[다이나믹 프로그래밍] ▲ 2293번 - 동전 1

[백준] 2293번 - 동전 1

(한줄평) 오랜만에 풀었더니 dp 문제 감을 잃었다고 느꼈다. 한 끝차이로 계속 틀린 이유을 찾지 못했던 문제.. 다음에 다시 풀어봐야할 것 같다

풀이 시간: 60분 이내

 

n가지 종류의 동전을 사용해서 가치의 합이 k원이 되는 경우의 수를 구하는 문제다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

---

(풀이1) 틀린 풀이

1) 문제 해결 아이디어

점화식을 세우기까지는 오랜시간이 걸리지 않았으나 그걸 코드로 구현하는 과정에서 잘못 생각한 부분이 있어서 어려움을 겪었다.

 

2) 소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())  # 동전 종류, 가치의합
graph = [int(input()) for _ in range(n)]  # n개의 동전 가치
d = [0] * (k + 1)  # 가치합이 i가 되는 경우의 수
d[0] = 1  # 동전을 1개 사용할 경우

for i in range(1, k + 1):
  for c in graph:
    if(i - c >= 0):
      d[i] += d[i - c]

print(d[k])  # 가치의 합이 k가 되는 경우의수

(풀이2) 정답 풀이

1) 문제 해결 아이디어

위 코드에서 바깥 for문과 안쪽 for문의 위치만 바꾸면 해결되는 문제였다.

 

1, 2, 5원 동전으로 10원을 만드는 경우라고 하자.

1) 1원짜리 동전으로 1원~10원 만들기

d[1] = d[2] = ... = d[10] = 1

2) 1, 2원짜리 동전으로 2원~10원 만들기

d[2] += d[0]

...

d[10] += d[8]

3) 1, 2, 5원짜리 동전으로 5원~10원 만들기

d[5] += d[0]

...

d[10] += d[5]

 

<점화식>

2) 소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())  # 동전 종류, 가치의합
graph = [int(input()) for _ in range(n)]  # n개의 동전 가치
d = [0] * (k + 1)  # 가치합이 i가 되는 경우의 수
d[0] = 1  # 동전을 1개 사용할 경우

# 동전 종류만큼 반복
for c in graph:
  # 마지막으로 쓴 동전이 c일 때
  for i in range(c, k + 1):
      d[i] += d[i - c]

print(d[k])  # 가치의 합이 k가 되는 경우의수

 

[참고] https://jshong1125.tistory.com/44

[백준/Python(파이썬)] 2293 동전 1