글 읽기 - 반례를 알고 싶습니다.

matthew624 2년 전 0

아래와 같이 코드를 짯고 질문게시판에 있던 예제들은 다 돌아가는데 아예 알고리즘이 틀린건가요?>.. 다 돌아가는데 7프로에서 틀렸다고 뜨네요 .ㅠㅠ

import sys
from itertools import combinations
input=sys.stdin.readline

n,k=map(int,input().split())
coin,tmp=[],[]
dp=[0 for i in range(k+1)]

#사용할 동전의 종류
for i in range(n):
    coin.append(int(input()))
# dp[n]은 n에서 사용할 동전을 뺀 수들중 최솟값에 사용동전 1개를 추가한경우
# 즉 사용할 동전이 1,2,5일때 dp[10]은 dp[9],dp[8],dp[5]의 최솟값중 1을 더한 것
for i in range(1,k+1):
    for j in coin:
        if(i-j>=0):
            tmp.append(dp[i-j])
    if(tmp==[]):
        dp[i]=-1
    else:
        dp[i]=min(tmp)+1
print(dp[k]) 

rhdqor213 2년 전 0

17번째 줄에서 tmp에 0으로 초기화된 dp를 추가하면 tmp는 18번째 줄 if문에 걸릴까요? 반례입니다.

input:
1 3
2
answer:
-1

matthew624 2년 전 1

아 ㅠㅠ 감사합니다 다시 해보니까 전체적으로 틀린 것 같네요 ㅜㅜ

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

문제

문제

출처

ICPC

반례를 알고 싶습니다.

matthew624 2년 전 0

rhdqor213 2년 전 0

matthew624 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말