[백준] 2293 동전 1 -골드 4

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DP
• 구현

---

1. 문제설명

 

N 가지 동전이 주어지고 만드려는 동전의 합 K가 주어질 때 동전의 합 K를 만드는 경우의 수를 출력하는 문제 입니다.

 

주어진 동전은 여러번 사용해도 합이 K원 되면 상관없고, 주어진 동전을 사용한 개수가 동일한데 순서가 다른 경우 이 경우는 동일한 경우로 생각합니다.

---

[제한사항]

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

---

2. 접근방식

 

지난 시간 풀었던 동전 2 문제와 굉장히 유사한 문제 입니다.

 

동전 2의 경우 주어진 경우의 수 중에서 더 적은 동전을 사용하는 경우를 골라 DP에 누적시키는 것이라면

 

이번 문제는 경우의 수 자체를 구하는 것이기에 min 과정이 사라졌다고 볼 수 있죠

 

이 문제를 해결하기위해 저번에 풀었던 동전 2 방식으로 접근해 보았습니다.

 

1원만 사용해서 동전을 만드는 경우 경우의 수는 모두 1가지 뿐입니다.

 

여기에 2원 동전이 섞이는 경우 입니다.

 

 

2원 동전이 섞이는 경우 경우의 수가 늘어 납니다.

4원의 경우 1 + 1 + 1 +1 / 1+ 1 + 2 / 2 + 2 로 경우가 3가지 존재하죠

 

기존의 1의 경우에 새롭게 4원을 만드는 경우의 수가 추가된 것입니다.

 

자세히 보면 2원의 경우의 수에 경우의 수가 1가지 늘어난 것과 동일하죠

 

2원을 만드는 경우의 수는 1 + 1 / 2 2가지 인데 2 + 2 가 늘어난 경우와 동일 합니다.

 

6원의 경우도 4원을 만드는 경우의 수에 1가지 추가되었고

 

8원 10원도 동일합니다.

 

즉, 이전 금액을 만든 경우의 수만큼 기존 경우의 수가 추가된 것이죠

 

1원을 이용해 전체를 만든 경우의 수에 2원의 경우의 수가 누적 되었습니다.

 

여기에 5원을 이용하는 경우의 수도 구해보죠

 

5원의 경우 5원을 활용할 수 있는 5원 부터 경우의 수가 늘어 났습니다.

 

기존의 경우의 수에 5원을 활용하는 경우의 수가 1가지 늘어나 4개가 되었고 6원부터 다시금 경우의 수를 계산해 주어야 합니다.

 

그러나 이는 자세히 보면 6원의 경우 기존의 경우의 수 4에서 1원의 경우의 수 1을 더해준 모양과 동일하고

7원의 경우 기존의 경우의 수 4에 2의 경우의 수 2를 더한 모양과 동일합니다.

8, 9, 10 역시 기존의 경우의 수에서 5원만큼 뺀 경우의 수를 다시금 더해준 모양과 동일하죠

 

이를 통해 점화식을 유추해보면 

 

for coin in coins 를 통해 전체 coin을 순회할 때 for j in range(coin, K + 1) 을 통해서 코인부터 목표금액 K원 까지 반복을 실시합니다.

 

이때 DP[j] 는 기존의 경우의 수에 coin을 뺀만큼의 경우의 수를 더해주어야 하니

DP[j] += DP[j - coin] 으로 작성할 수 있겠죠 코드로 보겠습니다.

---

3. 코드

import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]    # 코인 입력받기
DP = [0] * (K + 1)                          # DP 테이블 생성
DP[0] = 1                                   # 0원을 만드는 경우의 수는 1가지 뿐 0원을 이용하는 것

# 전체 코인을 순회하며 경우의 수 누적해주기
for coin in coins:
    for j in range(coin, K + 1):
        DP[j] += DP[j - coin]

# 목표 금액의 경우의 수 출력
print(DP[K])

---

[코드설명]

 

앞선 접근을 통해 점화식을 세웠고 기존에 동전 2 문제를 풀며 DP 테이블을 생성했던 방법과 비슷하게 문제를 접근하였습니다.

 

입력받은 전체 코인을 순회하며 DP 테이블에 누적합을 구해줍니다.

 

기존의 경우의 수에 새롭게 추가된 경우의 수를 더해주어야 하니 기존의 경우의 수 j번째에 coin만큼 뺀 경우의 수를 누적하여 더해주었습니다.

 

목표 금액 K원의 경우의 수를 찾아야 하니 찾아서 출력해주었습니다.

---

4. 결과

---

[회고]

약 1년전에 한번 풀었었던 문제 입니다. 

 

그때 틀렸던 코드를 살펴보면

 

동작 방식은 유사한데 DP 테이블을 초기화 해주지 않아서 틀렸습니다.

 

이번에도 마찬가지로 DP 테이블을 생성하고 초기화를 해주었어야 하는데

 

도저히 어떻게 초기화를 해보지가 생각나지 않았습니다.

 

처음에는 DP 테이블의 1번을 1로 초기화 하고 2부터 탐색을 시작할까 생각했는데 동전의 종류에서 1원이 주어지지 않는경우 틀린 조건이 되어서 고민을 많이 했습니다.

 

그러다 문득든 생각이 이번에는 동전을 이용해 K원을 구하는 경우를 찾는 문제 였고 0원을 만드는 경우는 0원을 이용하는 방법 뿐이었습니다. 

 

실제로 동전의 가치는 100,000 보다 작거나 같은 자연수라고 주어졌습니다. 자연수에 0이 들어가는지 아닌지는 명확히 알려진게 없지만 이번 문제에서 동전의 가치는 0보다 크다는 설명이 없었기 때문에 0원도 사용된다 생각하였고

 

DP 0을 초기화 하여서 풀어 문제를 해결할 수 있었습니다.

 

점화식의 경우 손으로 풀어보기전에 동전 2를 풀며 대략적으로 한번 풀었던 문제라 점화식 세우기가 더 쉬웠습니다.

 

그 후 문제를 풀고나서 검증의 과정으로 손으로 직접 다시 풀어보았고 동작과정을 더 제대로 이해하게 되었습니다.