[백준] 2294 동전 2 - 골드 5

[오늘의 문제]

https://www.acmicpc.net/problem/2294

---

[오늘의 학습 키워드]

• DP, 구현

---

1. 문제설명

 

N개의 동전으로 K원을 만들어야 하는데 동전을 최소한의 개수로 완성하는 프로그램을 작성하는 문제 입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 128MB
• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 10,000
• 동전의 가치는 100,000보다 작거나 같은 자연수이다.

---

2. 접근방식

이번 문제는 고민을 많이 했던 문제 입니다.

 

예전에 한번 풀었던 문제 인데도 방법이 잘 생각나지 않았습니다. 우선 주어진 예시를 토대로 최소한의 코인을 구하는 과정을

 

전체 로직을 통해 생각해 보았습니다.

 

주어진 코인의 종류를 통해서 목표 금액이 15원을 만드는 방법을 전체 생각해 보았습니다.

 

1원의 경우 목표 금액 15원을 만들기 위해 15개의 코인이 필요하고

 

5원의 경우 3개

 

12원의 경우 만들 수 없죠

 

그런데 주어진 코인들을 혼용하면 다르게 만들 수 있습니다.

 

 

여기서 주어진 코인들을 이용해 목표금액까지를 채워 보았죠

 

1원부터 15원 까지 필요한 코인의 개수를 모두 세어주었습니다.

 

 

for i in range(1, 15) 의 동작과 동일하죠

 

5원을 이용해 채우는 과정은 for i in range(5, 15)의 동작과 동일합니다.

 

이때 5원을 이용해 코인을 채울때 DP[5] 는 현재 5개가 존재하는데 5원 1개를 이용하는게 코인을 더 적게 소모합니다.

 

그럼 DP[5] 를 구하려면 최소값을 찾아 주어야 하니 

 

DP[5] = min(DP[5], DP[5 - 5] + 1) 로 설정하면 최소값을 찾을 수 있습니다.

 

현재 5원을 기준으로 DP[5] 는 5개의 코인을 이용해 채웠는데 5원 코인 1개로 대체하려면 DP[5]의 개수를 5개 빼주고 1로 바꿔줘야죠 그러나 하드코딩은 불가능 하니 규칙을 찾아주어야 합니다.

 

5개의 코인에서 5원을 빼면 0원이죠 이 0원을 만드는 코인의 개수는 0개 입니다. 여기에 5원 코인 1개를 이용하기 때문에 1을 더해주면 5원의 코인을 1개 이용해서 DP[5]를 채우는 것과 동일하죠

 

마찬가지로 DP[10]의 경우도 1원짜리 10개 보다는 5원짜리 2개가 더 코인을 적게 소모하고 이는

5원의 코인을 만들 때 들었던 코인의 개수에 1개만 더해주면 10원이 됩니다.

 

즉 DP[i] 번째 코인을 만들기 위해서는 DP[i - coin] + 1의 동작을 실시해주면 될 것입니다.

 

---

3. 코드

import sys
input = sys.stdin.readline

# 동전의 종류, 목표 금액
N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]

# 최소값을 구해야 하니 DP값을 적당히 큰 값으로 생성
DP = [10001] * (K + 1)
DP[0] = 0 # 0원을 만드는 방법은 0개의 코인 사용하기

# 코인을 순서대로 탐색
for coin in coins:
    # 현재 코인을 기준으로 목표금액 까지 채워보기
    for i in range(coin, K + 1):
        # 둘 중 더 적게 코인이 든 상황을 선택
        DP[i] = min(DP[i], DP[i - coin] + 1)

# 불가능하면 -1, 아니면 코인의 개수 출력
print(-1 if DP[K] == 10001 else DP[K])

---

[코드설명]

우선 코인이 사용되는 최소의 개수를 구해야 하니 DP 테이블은 문제에서 접근이 불가능한 적당히 큰 수로 생성해 주어야 합니다.

 

K가 최대 10,000이 주어지니 10001로 DP 테이블을 생성해 주었습니다.

 

그 후 min 조건을 충족하는 과정에서 앞서 5원의 코인을 만들때 0원의 개수에 +1을 해주었으니 인덱스 순서를 맞추기 위해 DP 테이블은 K  + 1개 만들어 주었고 0원은 0으로 초기화 해주었습니다.

 

그 다음 전체 코인을 하나씩 순회하며 해당 코인을 기준으로 목표 금액을 채워 나갑니다.

 

처음은 DP 테이블이 모두 10001로 생성될 테니 첫 코인의 개수로 모두 대체 되겠죠

 

4원의 경우 3원을 만드는데 들어간 코인의 개수에 현재 코인의 수 +1을 하니 4가 되고 이런식으로 15까지 채우게 되죠

 

5원의 경우 현재 코인의 가치 5원 빼주면 0원이 되고 0원을 만드는데 들어간 코인의 수는 0개이니 현재 코인의 개수 +1을 실시해 1이 됩니다.

 

이 과정을 반복하면 15원을 만드는 최소의 코인 개수를 구하게 되죠

 

그러나 출력시 DP[K] 번째 코인의 개수가 여전히 10001 이라면 해당 코인은 만들 수 없기 때문에 -1을 출력해주고 그게 아니라면 DP[k] 를 만드는데 들어간 코인의 개수를 출력해주면 됩니다.

---

4. 결과

---

[회고]

이번 문제는 예전에 한번 풀었었던 문제 입니다.

 

DP 문제를 많이 풀며 조건을 찾는 실력이 늘었다 생각했는데 골드 문제를 만나니 여실히 실력이 부족한게 느껴졌습니다.

 

DP 테이블을 초반에 어떻게 생성하냐가 이번 문제의 경우 가장 헷갈렸습니다.

 

처음에는 코인의 개수만큼 DP 테이블을 생성하고 해당 코인을 이용해 이용해 목표 금액이 K원을 만드는데 필요한 값을 누적으로 구해보려 했는데 최소의 개수를 구하는 문제 이다 보니 이런 방식으로는 문제가 해결되지 않는 것을 깨달았습니다.

 

따라서 목표 금액을 채우는 과정을 누적으로 계산해보기 위해 K원 까지의 DP 테이블을 생성하였고

 

해당 금액을 채워가며 목표 금액이 K원에 도달하고자 하였습니다.

 

그 다음 문제는 어떻게 해당 코인의 가치를 인식하고 점화식을 세우지가 문제 였는데 확실히 찾은 방법은 6원부터 10원을 만드는 과정에서 제대로 이해를 하였습니다.

 

현재 해당 금액을 채우기 위해서는 선택한 코인을 현재 금액에서 빼주면 선택한 코인을 이용해 최소한의 코인을 사용해 현재 금액을 채울 수 있었고 최소의 값을 확실히 구하기 위해서는 기존의 값과 새로운 값을 비교해 주어야 했습니다.

 

따라서 제대로 점화식을 세울 수 있었고 한번더 문제를 해결할 수 있었습니다.