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

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

2293번: 동전 1

DP 너무 어렵다에요

---

아이디어

1. DP

• 문제를 보고 dp문제인 것도 알고 'DP [k] = 합이 k가 되는 경우의 수'라는 것도 알았다.
• 근데 점화식 아이디어가 떠오르지 않아 검색의 힘을 빌렸다.
• 일주일 뒤에 또 풀어봤는데 또 까먹었다. 이해를 못 했다는 뜻이다.
• 이번 기회에 제대로 이해하고 넘어가기로 함.

---

코드 설명

DP = [0] * (k + 1)
DP[0] = 1
for c in coins:
    for i in range(c, k + 1):
        DP[i] += DP[i - c]

일단 코드는 정말 간단하다. 하나하나 뜯어보도록 하자.

 

먼저 문제에서 "사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다."라는 말은

예를 들어 합이 4가 되는 경우에서 '1 1 2'와 '2 1 1', '1 2 1'은 같은 경우로 취급한다는 뜻이다.

이걸 고려 안 하면 어떤 경우가 생기는지 다음 예시를 보면 된다. 알면 그냥 넘어가도 됨.

 

 

---

자 예를 들어서 동전 종류가 '1, 2'가 있고 k = 4, 합이 4가 되는 경우의 수를 구한다고 생각해보자.

그럼 일단 결과를 먼저 생각해보면 dp [4]에 3이 저장되야한다.

직접 경우를 적어보면 '1 1 1 1', '1 1 2', '2 2'로 3가지가 나와야 함.

 

그럼 내가 지금 1원이 있다고 생각하자. 여기서 나는 3원을 추가해 주면 4원이 된다.이 말은 3원을 만드는 경우에서 1원만 추가해주면 4원이 된다는 소리다.어 그럼 3원을 만드는 경우는 뭐가 있지라고 생각해보면 '1 1 1', '1 2'가 있다. 여기서 1원을 더하면 '1 1 1 1', '1 2 1' 두 가지 경우가 나온다.이렇게 되면 위에서 말한 같은 경우로 취급 문제가 생긴다. 

 

이게 무슨 소리냐. 이번에는 2원이 있다고 생각하자. 여기에 2원을 추가해주면 4원이 된다.2원을 만드는 경우는 '1 1', '2' 두 가지가 있다.여기에 2원을 더하면'1 1 2', '2 2' 두 가지가 된다.

 

정답은 3인데 위와 같은 방식으로 하니 경우의 수가 4가 된다.

'1 1 2'와 '1 2 1'을 다른 경우로 취급해서 생긴 문제다.

 

그럼 어떻게 해야 하나. 동전을 하나씩 넣는다고 생각하면 된다.

동전을 사용하는 가지 수를 늘려가며 dp값을 업데이트한다는 뜻이다. 

 

표로 나타내면 다음과 같다.

DP	0	1	2	3	4
c = 1일때	1	1	1 (1 1)	1 (1 1 1)	1 (1 1 1 1)
c = 2일때	1	1	2 (1 1, 2)	2 (1 1 1, 1 2)	3 (1 1 1 1, 1 1 2, 2 2)

 

이렇게 하면 '1 2'에 1원을 추가해서 4를 만드는 경우는 자동으로 제외된다.

왜냐 이미 '1 2'라는 것은 1원을 쓰고 2원을 썼다는 건데, 여기서 다시 1원을 쓸 수 없다!

실제 for문으로 생각해보면 c = 1일 때가 지나가고 c = 2일 때 다시 c = 1일 때로 돌아갈 수 없다는 말이다.

 

내가 이 얘기를 길게 한 이유는 인터넷에서 코드를 찾아볼 때 '이중 for문을 쓰는 것은 알겠는데 왜 coin리스트 for문이 먼저지?'에 대한 의문을 해결을 위함이었다.

 

따라서

DP [4] (1,2 원으로 4를 만드는 경우의 수) = DP[4] (원래 1원으로만 4를 만드는 경우의 수) + DP[4 - 2] (1, 2 원으로 2를 만드는 경우의 수, 여기서 2원만 추가해주면 4가 되니까.)

-> DP[i] += DP[i - c] 로 표현할 수 있다.

 

여기서 i - c가 음수가 되면 안 되니까 i는 c부터 시작하게 작성해야 한다.

2원으로 1원을 못만드는 것과 같은 말이다.

 

이렇게 코드를 작성하면 DP [0]의 값이 필요하다.

DP [0]이라는 것은 DP [k - k]라고 생각하면 쉽다.

내가 합이 k가 되게 만들 때, k원짜리 동전 하나만 쓰는 경우다.

그래서 초기에 DP[0] = 1을 저장한다. 

 

 

이차원 배열을 쓰면 좀 더 직관적으로 알아볼 수 있지만, 메모리 제한이 있어서 값들을 업데이트해주는 방식을 택해야 한다.

---

전체 코드

n, k = map(int, input().split())

coins = []
for i in range(n):
    coins.append(int(input()))
coins.sort()

DP = [0] * (k + 1)
DP[0] = 1
for c in coins:
    for i in range(c, k + 1):
        DP[i] += DP[i - c]
print(DP[k])