파이썬 알고리즘 204번 | [백준 2294번] 동전 2 DP

204. 동전2 DP

1) 어떤 전략(알고리즘)으로 해결?

dp ~

2) 코딩 설명

동전 갱신되는 과정

3 15
1
[0, 1, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]      
[0, 1, 2, 3, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1000001, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1000001, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1000001, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 1000001, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1000001, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 1000001]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

5
[0, 1, 2, 3, 4, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 11, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 12, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 13, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 14, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 15]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 3]

12
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 5, 6, 3]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 6, 3]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 3, 3]
[0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 3, 1, 2, 3, 3]

3

<내 풀이>

import sys

n,k = map(int, sys.stdin.readline().rstrip().split()) 
# 각각의 동전은 몇 개라도 사용
# 동전의 가치는 100,000보다 작거나 같은 자연수
price =[1000001 for _ in range(k+1)] # 가격만큼 배열 만들어
price[0]=0

for co in range(n) :
    value = int(sys.stdin.readline().rstrip()) #동전 가격
    for i in range(value, k+1) : # 내 가치 이상부터  ~
        price[i] = min(price[i], price[i-value]+1)

# 마지막 칸이 갱신안된 상태면 -1 
if price[-1]!=1000001 : print(price[-1])
else : print(-1)

<내 틀렸던 풀이, 문제점>

92%에서 틀리는 풀이

아 맞당 불가능한 경우 예외처리 안함 ;;

import sys

n,k = map(int, sys.stdin.readline().rstrip().split()) 
# 각각의 동전은 몇 개라도 사용
price =[1000001 for _ in range(k+1)] # 가격만큼 배열 만들어
price[0]=0

for co in range(n) :
    value = int(sys.stdin.readline().rstrip()) #동전 가격
    for i in range(value, k+1) : # 내 가치 이상부터  ~
        price[i] = min(price[i], price[i-value]+1)
    #print(price)

print(min(price))

<반성 점>

• 예외처리까지 잘해주자!

<배운 점>