백준 2293 (동전 1)
백준 2293 (동전 1)
문제 링크
문제 링크 : https://www.acmicpc.net/problem/2293
문제 접근
반갑습니다. 오늘도 동적 계획법 문제를 들고 왔습니다. n가지 종류의 동전이 있습니다. 동전의 수는 제한이 없을 때, 적절히 사용해서 k원을 만드는 문제입니다. 아시는 분은 아시겠지만, 이 문제는 동적 계획법 국룰 문제입니다. 뭔가, value원을 만들고 싶을 때, 이전에 만들었던 value들을 적절하게 사용한다면 해결할 수 있을 것 같습니다.
그렇다면 아래 코드를 한번 봅시다. 이 코드가 과연 맞는 코드일까요?
1
2
3
4
5
dp=[1 for _ in range(k+1)] # dp[0]=1이라서, 1로 초기화를 했습니다.
for value in range(1,k+1) :
for now_coin in coins :
if value-now_coin>=0 :
dp[value]+=dp[value-now_coin]
얼핏 봤을 때는, 맞다고 생각할 수 있습니다. 하지만 이는 아주 중요한 문제를 포함하지 않고 있습니다. 바로 실수 체계에서 덧셈은 교환 법칙이 성립한다는 사실을 무시하는 코드입니다.
정답을 말하자면, dp[value-now_coin]에서 now_coin을 추가한 경우의 수가 교환 법칙에 의해 중복이 될 수 있다는 사실입니다. 예시를 들어보자면, 현재 coins는 1,2,5로 주어져 있습니다.
1
2
3
4
5
6
7
8
dp[1]은 1을 사용하는 한 가지 경우입니다. 따라서 dp[1]=1입니다.
dp[2]는 1+1, 2 두 가지 경우입니다. 따라서 dp[2]는 2입니다.
위는 자명한 사실입니다.
dp[3]이 문제가 됩니다. 위 코드에 의거하면
1) dp[3]은 dp[1]에 2원을 추가한 경우
2) dp[3]은 dp[2]에 1원을 추가한 경우입니다.
따라서 dp[3]은 3입니다.
하지만 3을 만드는 경우의 수는 1+1+1, 2+1(=1+2)인 두 가지 경우입니다. 위 코드대로라면, 1+1+1, 2+1, 1+2로 총 세가지 경우를 갖게 됩니다. 하지만 1+2와 2+1은 사실은 같습니다. 제가 덧셈의 교환법칙은 무시해버렸다는 의미가 여기 있습니다.
그렇다면 어떻게 해결을 해야 합니까? 학창시절, 확률과 통계 경우의 수 단원에서 이러한 문제를 많던 기억이 납니다. 이런 문제를 해결하기 위해서, 일관성있게 문제를 풀어야 했습니다. 즉, 프로그래밍 관점으로 이러한 문제를 풀기 위해서, 일관성 있도록 그리고 교환 법칙에 의거하여 같은 케이스를 다르게 보지 않도록 하는 것이 요점입니다.
간단한 문제 푸는데 뭐 이렇게 길고 어렵게 글을 적냐고 할 수 있지만, 뜯어보면 나름 배울 것이 많은 문제라 그렇습니다. 그렇다면 일관성있게 어떻게 하는데? 라는 질문을 해봅시다.
10원을 만드는 것이 목표고, (1,2,5)원이 있다고 생각해보겠습니다. 한 번 쫙 나열해봅시다.
1
2
3
4
5
6
7
8
9
10
11
1+1+1....+1
1+1+1....+2
1+1+1....+5
1+1+1..+2+2
... 중략
1+2+2+...+2 -> 안 되는 케이스입니다. 이해를 돕기 위해 적었습니다.
1+2+2+...+5
1+5+...+5 -> 안 되는 케이스입니다. 이해를 돕기 위해 적었습니다.
2+2+...+5 -> 안 되는 케이스입니다. 이해를 돕기 위해 적었습니다.
2+5.. -> 안 되는 케이스입니다. 이해를 돕기 위해 적었습니다.
5+5..
이를 테면, 배낭 문제와 결이 같다는 것입니다. 처음에 coin[0]만을 고려해서 target을 만들고, 이후 coin[1]까지 고려해서 target을 만들고. . 이후 coin[final]까지 모두 고려해서 target을 만들자는 의미입니다.
그렇다면 코드를 작성할 수 있습니다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
import sys
n,k=map(int,sys.stdin.readline().split())
dp=[0 for _ in range(k+1) ]
coins=[int(sys.stdin.readline()) for _ in range(n)]
dp[0]=1
for coin in coins :
for target in range(1, k+1) :
if target-coin>=0 :
dp[target]+=dp[target-coin]
print(dp[k])
메모리가 4MB로 주어졌기에, 굳이 2차원 배열을 만들지 않고, 1차원 배열에서 모든 것을 해결했습니다. 2차원 배열을 사용해서 점화식을 적는다면
1
dp[i][value] = i번째 코인 까지 사용해서, value원을 만들 때 경우의 수
라고 작성할 수 있습니다. 저는 이 과정을 2차원 배열을 사용하지 않고 1차원 배열을 사용했을 뿐입니다.
마무리하며
저는 블로그 글을 작성할 때, 최대한 자세하게 작성하려고 노력합니다. 그 과정에서 너무나 당연하다고 생각하던 문제를 논리적으로 기술할 때 머릿속의 내용이 정리 되면서 한층 성장하는 기분과 재미를 느낍니다. 아무튼 여러분들도 그런 과정을 거쳐 보시길 . ..