글 읽기 - 이해가 안되는 부분이있어서 올려봅니다(문제는 맞았습니다)

seachan94 5년 전 0

최소동전 갯수로 만드는 것이여서

원래는 부분 1을 if(j%coin[i]==0)dp[j]=j/coin[I]로 했었습니다. 근데 틀리더군요

그래서 현재 if(j%coin[i]==0)dp[j]=min(dp[j],j/coin[I]) 이렇게 바꿨는데 맞았습니다.

사실 저는 부분 2에서 그냥 나누는 것 보다 더 적은 동전을 사용하여 어떤 수를 만들 수 있는 것을 다 판별해준다는 생각이거든요.

(예를들어 동전이 3. 9가 있을 때 12 인경우에 3의동전을 4개 쓰는 것보다 9하나 3하나 쓰는데 동전을 덜 쓰는 것임으로 12의 값은 2개가 된다고 생각합니다. )

이걸 생각해서 포함시킨 부분이 2부분 입니다.)

그럼 제가 처음에 부분1을 했던것처럼 해도 상관없지않나요?

#include<iostream>
#include<vector>
using namespace std;
int min(int a,int b){
    if(a==0)return b;
    if(b==0)return a;
    if(a>b)return b;
    else return a;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    vector<int> coin(n);
    vector<int> dp(k+1);
    for(int i=0;i<n;i++)cin>>coin[i];
    for(int i=0;i<n;i++){
        for(int j=coin[i];j<=k;j++){
            if(j%coin[i]==0)dp[j]=min(dp[j],j/coin[i]);//부분 1
            if(dp[j-coin[i]]!=0)dp[j]=min(dp[j],dp[j-coin[i]]+dp[coin[i]]);//부분2
        }
    }
    if(dp[k]==0)cout<<"-1";
    else cout<<dp[k];
}

njw1204 5년 전 0

동전 순서가 오름차순으로 주어지는게 아니라서

이러한 반례가 있습니다.

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

문제

문제

출처

ICPC

이해가 안되는 부분이있어서 올려봅니다(문제는 맞았습니다)

seachan94 5년 전 0

njw1204 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말