글 읽기 - 동전2 왜 틀렸을까요 ㅠㅠ

dbsgk1102 6년 전 0

생각되는 모든 테스트 케이스를 넣어봐도 다 맞는데 틀렸다고 뜹니다...

DP초보에게 도움의 손길을 주세요!

#include <stdio.h>
int dp[100001][2];// dp[i][0]-> 쓴 액수가 i일때 쓰인 동전의 갯수.
// dp[i][1] 연산을 한번도 진행하지 않았을경우 0
int coin[1000];// 동전의 가치.
int main()
{
    int n,price,i=0,j,tmp;
    scanf("%d %d",&n,&price);
    for(i=0;i<n;i++)
        scanf("%d",&coin[i]);
    i=0;
    while(i<price)
    {
        i++;
        for(j=0;j<n;j++)//coin배열 0 ~ n-1 돌리기
        {
            if(dp[i][1]==0)//한번도 연산을 진행하지 않았을 때
            {
                if(i==coin[j])//기초 베이스 동전갯수
                {
                    dp[i][1]++;
                    dp[i][0]++;
                }
                else if(i>=coin[j])//동전가치보다 큰 i일때 (본격적 연산)
                {
                    if(dp[i-coin[j]][1]!=0)// 전의 경우에서 연산이 되었을 경우
                    {
                        dp[i][0]=dp[i-coin[j]][0]+1;
                        dp[i][1]++;
                    }
                }
            }
            else//한번이라도 연산을 했을 때
            {
                if(i>=coin[j])// 세그멘테이션 방지
                {
                    if(dp[i][0]>dp[i-coin[j]][0]+1)//사용한 동전의 최솟값
                        if(dp[i-coin[j]][1]!=0)// 전의 경우에서 연산이 되었을 경우
                        {
                            dp[i][0]=dp[i-coin[j]][0]+1;
                            dp[i][1]++;
                        }
                }
            }
        }
    }
    if(dp[price][0]==0)
        printf("%d\n",-1);
    else
        printf("%d\n",dp[price][0]);
    return 0;
}

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

문제

문제

출처

ICPC

동전2 왜 틀렸을까요 ㅠㅠ

dbsgk1102 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말