[백준] (Python) 2293번 - 동전1 (골드5, dp)

기업 코딩테스트 연습을 위해 python으로 문제풀이 하였습니다. 😅

 

⚫️ 문제

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

2293번: 동전 1

 

⚫️ 나의 풀이

내가 처음에 한 생각은 다음과 같다.

dp[i] 에 i를 만들기 위한 경우의수를 넣고자 했다. 근데,,, 규칙도 보이지 않을 뿐더러 주어진 수로 어떻게 경우의수를 세어야하는지 감이 안왔다.  예를들어, i = 5 이고 주어진 수가 1, 2, 5 라면 5에서 1을 빼면서 1이 몇개 필요할지 세어주고, 또다시 5에서 2를 빼면서 조합을 찾아주고.. 이런방식을 생각해봤지만, 이렇게 모든경우의 수를 세어서 넣어주는 방식을 사용하면 '큰 문제를 작은문제로 쪼개서 생각하는' dp 의 풀이 방식과는 멀어지고, n이 100개, k가 10000으로 주어지면, 100 * 100 * 10000 연산을 수행하게 된다. 말도안된다 ㅠㅠ 

어떻게 dp를 구성해야할지 고민하다가, 결국 인터넷의 힌트를 조금 얻었다. .. 하... 왤케 어려운거야 ㅠ

우선 나의 첫번째 접근방식이 완전히 틀리진 않았다. i를 구하는 경우의수를 dp에 넣는 방식은 비슷했따. 하지만 그 경우의수를 구하는 방식이 달랐다.

이 예제에서 우리는 동전 1, 2, 5를 갖고 있다. 여기서 나는 dp 하나를 구하기 위해서 모든경우의수를 한번에 세어주려고 했지만, 따로 세어주면 규칙성을 발견할 수 있었다.

1. 1을 사용해서 i를 만들 수 있는 경우
2. 2를 포함해서 i를 만들 수 있는 경우 (1과 2)
3. 5를 포함해서 i를 만들 수 있는 경우 (1 , 2, 5)

이렇게 세 가지 경우로 세어주면 규칙성을 발견할 수 있다. 우선, 우리가 당연하게 아는 사실은 2를 이용하고 싶으면 2이상의 수가 만들어지는 것과 5를 이용하고 싶다면 5이상의 수를 만들어야한다는 것이다. 이런 관점에서 그림을 그려가며 규칙을 찾아보면, 아래와 같은 점화식이 나온다.

보라색 -> 보라색점화식, 연두색 -> 연두색 점화식

이렇게 구할 수 있다. 구현은? 이중 for문을 이용해서 구현할 수 있다.

 

⚫️ 정답코드

n, k = map(int, input().split())
coin = []
for _ in range(0, n):
    coin.append(int(input()))

dp = [0] * (k+1)
dp[0] = 1

for c in coin:
    for i in range(c, k+1):
        dp[i] = dp[i] + dp[i-c]

print(dp[k])