#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 101;
const int MAX_K = 10001;
const int IMPOSSIBLE = 1000000000;
 
int N, K, cost[MAX_N], dp[MAX_N][MAX_K];
 
int coin(int n, int k){
    if(n == N) return (k==0 ? 0 : IMPOSSIBLE); // base case
    if(dp[n][k] != -1) return dp[n][k]; // 이미 계산됨
 
    int result = coin(n+1, k);
    if(k >= cost[n]) result = min(result, coin(n, k-cost[n]) + 1);
    dp[n][k] = result; // dp 배열 값 갱신
    return result;
}
 
int main(){
    scanf("%d %d", &N, &K);
    for(int i=0; i<N; i++)
        scanf("%d", cost+i);
    // dp 배열 초기화
    for(int i=0; i<=N; i++)
        for(int j=0; j<=K; j++)
            dp[i][j] = -1;
    // dp로 문제 품
    int result = coin(0, K);
    if(result == IMPOSSIBLE) puts("-1");
    else printf("%d\n", result);
}

이거랑


import sys


def coin(n, k):
if n == N:
if k == 0:
return 0
 else:
return impossible
if dp[n][k] != -1:
return dp[n][k]

tmp_result = coin(n+1, k)
if k >= cost[n]:
tmp_result = min(tmp_result, coin(n, k-cost[n])+1)
dp[n][k] = tmp_result
return tmp_result


if __name__ == "__main__":
N, K = map(int, sys.stdin.readline().split())
cost = []
for i in range(N):
cost.append(int(sys.stdin.readline()))
sorted(cost)
dp = [[-1]*10001]*101
 impossible = 1000000000
 result = coin(0, K)
if result == impossible:
print("-1\n")
else:
print(result)

이 코드 두개가 테스트 결과 위에거는 맞고 밑에거는 틀렸대


참고로 백준 동전2(2294) 푸는 코드인데


대체 어디가 달라서 두개가 다른 코드라고 나오는거임????