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

인프런 커뮤니티 질문&답변

google_user

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

7-I와 실수형연산의 한계

해결된 질문

작성

121

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]);
            }
        }

지금 제가 생각하기에, 코드를 이렇게 짰을때, 일차원배열과 이차원배열이 큰 차이가 있나 싶기도하고, 다른 냅색문제에서 이렇게해서 통과하는 경우가 있었기에,

어떤 차이가 있을까, 반례가 뭐가있을까 질문드리고 싶습니다.

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 google님 ㅎㅎ

dp를 이차원 배열로 만들어서 n번째 인덱스까지 돈m을 썼을때의 최대 칼로리 양을 저장하게 했습니다.

무슨 코드인지 이해했습니다. 괜찮은 로직입니다. ㅎㅎ

#include <bits/stdc++.h>
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\n", mx); 
    }

    return 0;
}

다만 이렇게 해야 되지 않을까요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

google_user

작성한 질문수

전체 Q&A

질문하기