dp를 이차원 배열로 만들어서 풀어봤는데, 틀립니다.

Question

http://boj.kr/7c9fc1fdb4894c518c897537de03f02b 선생님, 안녕하세요~ dp를 이차원 배열로 만들어서 n번째 인덱스까지 돈m을 썼을때의 최대 칼로리 양을 저장하게 했습니다.   int dp[5004][10004]; // n번째 인덱스까지 돈m을 썼을때 최대 칼로리양 그 후 나머지 부분은, 동전문제에서 했던 것과 비슷하게, 단지 이차원 배열이니깐 dp[i][j]를 비교할 때, 가격이 이전 인덱스가 더 큰지, 아니면 이번 인덱스에서 가격만큼을 빼고 칼로리만큼을 더한게 더 큰지 비교해주도록 했는데요. for (int i = 1; i <= n; i++) { for (int j = 1 * 100; j <= m * 100; j++) { if (price[i] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - price[i]] + cal[i]); } mx = max(mx, dp[i][j]); } } 지금 제가 생각하기에, 코드를 이렇게 짰을때, 일차원배열과 이차원배열이 큰 차이가 있나 싶기도하고, 다른 냅색문제에서 이렇게해서 통과하는 경우가 있었기에, 어떤 차이가 있을까, 반례가 뭐가있을까 질문드리고 싶습니다.

큰돌 · Answer

안녕하세요 google님 ㅎㅎ dp를 이차원 배열로 만들어서 n번째 인덱스까지 돈m을 썼을때의 최대 칼로리 양을 저장하게 했습니다. >> 무슨 코드인지 이해했습니다. 괜찮은 로직입니다. ㅎㅎ #include using namespace std; int n, c; double m, p; int dp[5004][10004]; int cal[5004]; int price[5004]; int m1, m2; int main() { while (true) { scanf("%d %d.%d", &n, &m1, &m2); int max_price = m1 * 100 + m2; if (n == 0) { break; } for (int i = 1; i <= n; i++) { scanf("%d %d.%d", &c, &m1, &m2); cal[i] = c; price[i] = m1 * 100 + m2; } int mx = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= max_price; j++) { if (price[i] > j) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - price[i]] + cal[i]); } mx = max(mx, dp[i][j]); } } printf("%d ", mx); } return 0; } 다만 이렇게 해야 되지 않을까요? 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.