[백준] 2293 : 동전 1 (Python)

정답코드

n, k = map(int, input().split())
c = [int(input()) for _ in range(n)] # 코인 종류
dp = [0]*(k+1) # dp[k] = 합이 k원이 되는 경우의 수
dp[0] = 1 # 동전을 1개만 쓸 때의 경우의 수 업데이트를 위해

for i in c:
    for j in range(i, k+1):
        dp[j] += dp[j-i]
print(dp[k])

풀이는 주석에.

참고 블로그

dp[0] = 1을 하고싶지 않아 밑에 코드로 수정하였는데, IndexError가 발생하였다.

수정했는데 틀린 코드

n, k = map(int, input().split())
c = [int(input()) for _ in range(n)] # 코인 종류
dp = [0]*(k+1) # dp[k] = 합이 k원이 되는 경우의 수

for i in c:
    dp[i] += 1
    for j in range(i+1, k+1):
        dp[j] += dp[j-i]
print(dp[k])

위에 정답 코드는

for i in c:
    for j in range(i, k+1):

을 통해서 동전의 가치가 k보다 크면 for j in 안 코드가 돌아가지 않았다.
그런데 for j 밖에 dp[i] += 1을 추가하는 순간, k보다 큰 가치를 가진 동전이 존재할 때 인덱스에러가 발생한다.

때문에 dp[0] = 1로 하고싶지 않다면 for i in c: 에 if문으로 i<k 조건을 추가해줘야 한다.

수정의 수정을 통해 고친 코드

n, k = map(int, input().split())
c = [int(input()) for _ in range(n)] # 코인 종류
dp = [0]*(k+1) # dp[k] = 합이 k원이 되는 경우의 수

for i in c:
    if i < k+1:
        dp[i] += 1
    for j in range(i, k+1):
        dp[j] += dp[j-i]
print(dp[k])

결론 : 그냥 dp[0]=1로 하자. 그게 더 빠르다.