[Week 2] PACKING self review - Yunhyunjo

[Yunhyunjo]

PACKING self review

1. 해결 시도 과정

일단 절박도를 최대화는 백준 배낭문제 처럼 똑같이 구현을 하였습니다. 그리고 짐의 목록과 개수를 출력해 주어야하기 때문에 추가적으로 저장할 배열을 선언한 뒤 계산해 주었습니다.

2. 작성한 코드와 설명

vector <pair <int, int>> v(n+1);
vector <string> s(n+1);
v.push_back({ 0,0 });
s.push_back("");
for (int i = 1; i <= n; i++) {
	cin >> s[i] >> v[i].first >> v[i].second;
}

일단은 s에는 짐을, v에는 무게와 절박도를 같이 입력받아야하기 때문에 pair로 선언을 해서 입력받았습니다.

vector <vector <int>> dp(n + 1, vector <int>(k + 1));
vector <vector <int>> ss(k + 1);
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= k; j++) {
		if (v[i].first > j) {
			dp[i][j] = dp[i - 1][j];
		}
		else {
			dp[i][j] = max(dp[i - 1][j - v[i].first] + v[i].second, dp[i - 1][j]);
			if (dp[i][j] != dp[i - 1][j]) {
				ss[j].clear();
				ss[j] = ss [j - v[i].first];
				ss[j].push_back(i);
			}
		}
	}
}

행은 짐, 열은 무게로 2차 배열 dp를 선언해 준 뒤, 계산을 해가면서 더 큰 절박도를 저장해 주었습니다.
짐의 목록과 개수도 출력해 줘야하기 때문에 어떠한 짐을 선택했는지도 저장해 주었습니다.

3. 막힌 점 및 개선 사항

절박도 계산은 정확하게 나오는데 짐을 계산하는 과정에서 잘못된 부분이 있었던 것 같습니다. 제 코드의 짐을 저장하는 방식을 다시 이해해 봐야할 것 같습니다.

[Queue-ri]

코드 보니까 말씀하신대로 절박도 계산하는 부분은 문제가 없고, 답을 추적하는 과정의 로직이 잘못된 것 같습니다.

일단 절박도 구하는 도중에 추적을 하시면 안되고, 절박도 계산 다 끝난 상태에서 재귀함수로 추적 로직 작성해보세요.

(다른 코드 채점해서 AC 받으신것도 봤는데 그건 절박도 계산과 string DP를 같이 하는거라서 현조님 코드의 상황과 다릅니다.)

현조님 코드에 추적하는 부분만 수정하니까 AC 나오더라고요!

PS. 반복문으로도 추적 됩니다.

int count(int n, int k, vector <vector <int>>& dp, vector <pair <int, int>>& v, vector <int>& ss)
{
	int sum = 0;
	for (int i = n; i > 0; --i) {
		if (dp[i][k] != dp[i - 1][k]) {
			sum += 1;
			k -= v[i].first;
			ss.push_back(i);
		}
	}
	return sum;
}