글 읽기 - 동전2 반례 하나만 찾아주세요...

guillaume007 5년 전 0

질문에 나온 케이스는 다 찾아봤는데... 아직 반례를 못찾았네요 ㅠㅠ

#include<bits/stdc++.h>
using namespace std;

const int UNABLE = 1000000000;
int coin[101];
int dp[10001][101];

int sol(int n, int k){
    if(n == 0)
        return (k == 0 ? 0 : UNABLE);
    if(dp[n][k] != -1)
        return dp[n][k];

    int ret = sol(n-1, k);
    if(k >= coin[n])
        ret = min(ret, sol(n, k - coin[n]) + 1);
    dp[n][k] = ret;
    return ret;
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    for(int i = 1; i <= n; i++)
        scanf("%d", coin+i);

    for(int i = 0; i <= 10000; i++)
        for(int j = 0; j <= 100; j++)
            dp[i][j] = -1;

    int ans = sol(n, k);
    if(ans == UNABLE)
        printf("%d", -1);
    else
        printf("%d", ans);
    return 0;
}

lovinix 5년 전 1

6번째 줄을 dp[101][10001]로 수정하시고

28~29 줄을 범위에 맞게 초기화해주시면 맞는 코드입니다.

guillaume007 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

동전2 반례 하나만 찾아주세요...

guillaume007 5년 전 0

lovinix 5년 전 1

guillaume007 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말