글 읽기 - 왜 순서를 바꾸면 오답이 될까요?

wonjnlee 6년 전 0

DP로 풀었습니다.

궁금한점은 제가 동전의 액수를 담아놓은 배열의 순서를

{500, 100, 50, 10, 5, 1}과 같이 내림차순으로 하면 오답이 나오는데

지금 답으로 놓은 것 처럼 {1, 5, 10, 50, 100, 500}으로 하면 정답이 되네요.

어차피 min으로 최소값 처리를 하게 될 경우 답은 정상적으로 최소값이 나오지 않을까요?

궁금하네요..

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 1000

int dp[MAX + 1];

// 이 부분을 {500, 100, 50, 10, 5, 1}로 할 경우 오답 발생
int species[7] = {1, 5, 10, 50, 100, 500};

int main(void)
{
    int price, change;
    cin>>price;
    change = 1000 - price;
    
    dp[0] = 0;
    for(int i=1; i<=change; i++) {
        dp[i] = MAX;
        for(int j=0; j<6; j++) {
            if(species[j] <= i) {
                dp[i] = min(dp[i], dp[i - species[j]]) + 1;
            }
        }
    }
    cout<<dp[change]<<endl;
    return 0;
}

exqt 6년 전 0

27번째 +1이 min안에 들어가야 합니다

dp[i] = min(dp[i], dp[i - species[j]]+1)

wonjnlee 6년 전 0

아. 그러네요..

근데 어떻게 풀렸지;;;ㅋㅋㅋㅋ 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 순서를 바꾸면 오답이 될까요?

wonjnlee 6년 전 0

exqt 6년 전 0

wonjnlee 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말