백준 알고리즘 2294: 동전 2 (Python)

백준 알고리즘 1931: 회의실 배정 (Python)

백준 알고리즘 1931: 회의실 배정 (Python)

---

문제 해결을 위한 과정

이 문제는 일반적인 그리디를 이용한 방법으로는 해결할 수 없습니다. 그 이유는 그리디를 이용한 방법은 각 동전끼리 배수 관계를 가지고 있어야 합니다. ex) 1, 10, 100, 1000

이 문제의 예시를 보면 1, 5 12 등 배수 관계가 아니므로 dp를 이용해야 함을 알 수 있습니다.

과정을 설명하면 다음과 같습니다.

 

2 9

1

5 

를 예시로 하겠습니다.

 

1. dp 배열 선언 단, 0번째는 0으로 선언 나머지는 INF(1,000,000,000)로 선언

0

INF

INF

INF

INF

INF

INF

INF

INF

INF

 

2. 첫 번째 동전을 기준으로 for문을 돌리면서 해당 금액이 이전 동전 + 1개로 가능한지 확인

0

1

2

3

4

5

6

7

8

9

이 경우는 각 금액이 1원으로 무조건 가능하기 때문이다.

 

3. 두번째 동전을 기준으로 for문을 돌리면서 해당 금액이 이전 동전 + 1개로 가능한지 확인

0

1

2

3

4

1

2

3

4

5

이 경우는 5원 => 5원, 6원 => 1 + 5원, 7원 => 1 + 1 + 5원, 8원 => 1 + 1+ 1 + 5원, 9원 1 + 1 + 1 + 1 + 5원으로 가능하기 때문이다.

---

소스코드

n, k = map(int, input().split())
coins = []
for _ in range(n):
  coins.append(int(input()))
INF = int(1e9)
dp = [INF] * (k + 1)
dp[0] = 0

for coin in coins:
  for i in range(1, k + 1):
    if i - coin >= 0:
      dp[i] = min(dp[i], dp[i-coin] + 1)

if dp[k] == INF:
  print(-1)
else:
  print(dp[k])