[C++] 백준 2293번 동전 1

다이나믹 프로그래밍 문제.

처음에 문제에 접근할 때, 재귀함수로 접근하려 했는데 시간제한을 보고 포기했고,

알고리즘 분류를 보고 DP인 것을 봐도 어떻게 풀어야 할 지 감이 잘 오지 않았던 문제.

많이 고민해봤지만 생각하기 어려워서 결국 솔루션을 보고 해결했다.

이런 방법으로 생각할 수도 있구나라고 생각했다.

풀이를 정리할 겸 글을 적는다.

 

문제 풀이

먼저 DP문제를 풀 때에는 항상 규칙을 찾아야 한다. 어떻게 Bottom Up 방식을 적용할 것인지 생각해야한다.

예시 케이스인 n = 3 / {1, 2, 5}, k = 5일때의 규칙을 찾아 보자면

	1	2	3	4	5	6	7	8	9	10
1가지 { 1 }	1	1	1	1	1	1	1	1	1	1
2가지 { 1, 2 }	1	2	2	3	3	4	4	5	5	6
3가지 { 1, 2, 5 }	1	2	2	3	4	5	6	7	8	10

위 표가 각 수의 1 ~ n가지를 썼을 때 나타낼 수 있는 가짓수이다.

밑줄쳐진 파랑색 글자들은 모두 잘 보면 가지고 있는 동전의 값이 추가됐을 때라는 것을 알 수 있다.

규칙이 무엇일까?

우선, 한가지만 사용한다면, 1부터 10까지는 모두 한가지로만 나타낼 수 있다.

두가지를 사용한다면, 1은 어차피 한가지로밖에 못 나타내므로 의미가 없다.

그래서 파란색으로 된, 밑줄쳐진 글자에서부터 업데이트를 시작하면 된다.

이게 무슨 의미냐면, 한 가지의 동전이 추가 됐을 때, 내가 원하는 값에서 사용할 수 있는 가지수를 구하는 방법은 두 가지이다.

1. 추가된 동전의 값과 같은 값일 경우 : 이전 가지수에서 추가된 동전만 넣으면 그게 가지수이므로 +1
2. 추가된 동전과 다른 값일 경우 : 이 값을 p라고 한다면, p 값을 나타내기 위해선, (p - 동전의 값)이 몇 가지수 인지 알아야 한다. (p - 동전의 값)의 가지수에서 동전의 값만 각 가지수에 넣어주면 그게 바로 p의 추가된 동전에서의 가지수가 된다. 그리고 여기에 동전이 추가되기 이전에 가지수를 더해주면 된다.

 

2번 조건이 꽤 설명하기가 어려운데 차근차근 다시 정리해보겠다. (1번 조건이 아닌 경우라고 가정)

• 추가된 동전의 값을 value라 하고, 현재 가지수를 i라고 하겠다. 그리고 찾기 원하는 값을 p라고 하겠다.
• p는 (p - value) + value이다. 이 말은, (p - value)가 나타낸 가지수와 이 추가된 동전에서의 p에서의 가지수와 같다는 것을 의미한다. 왜냐하면 각 가지마다 value만 넣어주면 되기 때문이다.
• 그러면 동전이 추가되기 전, 즉 value를 고려하지 않은 p의 가지수에, (p-value)의 가지수를 더해주면 된다.

예시케이스에서 10의 가지수를 구하기 위해서는 

1. 한가지를 사용할 때는 동전 1의 가치이므로, 10은 9의 방법에서 1만 추가해주면 되는 것이다.
2. 두가지를 사용했을 때는 동전 2의 가치가 추가된 것이므로, 10은 8의 방법에서 2만 추가해주고 1가지를 사용할 때를 더해준다.
3. 세가지를 사용했을 때는 동전 5의 가치가 추가된 것이므로, 10은 5의 방법에서 5만 추가해주고 2가지를 사용할 때를 더해준다.

약간 Top-Down처럼 소개했는데 결국에는

• 한가지에서는 2가 1을 보고, 3이 2를 보고, 4가 3을 보고 ...
• 두가지에서는 3이 1을 보고 + 3의 한가지 방법의 수, 4가 2를 보고 + 4의 한가지 방법의 수, 5가 3을 보고 ... 
• 세가지에서는 6이 1을 보고 + 6의 두가지 방법의 수, 7이 2를 보고 + 7의 한가지 방법의 수, 8이 3을 보고 ...

 

정리를 이 쯤 하면 많이 한 것 같다. 코드를 살펴보자.

사용한 STL과 변수

STL은 특별히 필요가 없었다.

입력받는 n과 k, n가지 동전의 값을 저장한 value배열,

그리고 각 값마다 n가지 동전을 저장할 때 몇 가지 경우의 수가 있는지 저장할 dp배열이 있다.

 

처음에는 각 자리수를 따로 생각해서 dp[101][10001]로 생각했는데, 이렇게 만들면

이 문제의 메모리 제한에 걸리게 된다.

4MB = 4,000KB, 4,000,000B 인데, 위처럼 만들면 int가 4B이므로 메모리 초과현상이 발생한다.

따라서 자리수를 따로 나눠놓지 않고, 있는 값 그대로에서 업데이트 하는 방식으로 풀어야 한다.

 

메인함수

먼저, n과 k를 입력받고 n가지 동전의 값을 입력받고 저장한다.

 

이중 for문을 통해서 위에서 고려한 사항들을 해결해준다.

• 바깥쪽 for문은 고려하는 동전의 수가 몇 개인지를 고려하는 for문이다.
• 안쪽 for문은 추가되는 동전에 따라 경우의 수가 어떻게 바뀌는지를 고려하는 for문이다.

안쪽 for문에서, for문의 시작값이 value[i]로 되어있는데, 어차피 value[i]보다 작은 값들은 업데이트가 되지 않는다.

왜냐하면 위에서 고려했듯이,

1. 추가된 동전의 값과 같은 값이라면 이전 가지수에서 그 동전만 있는 경우만 추가하면 되므로 + 1
2. 추가된 동전과 다른 값이라면 이전 가지수 + (현재 값 - value[i])에서의 가지수

로 업데이트 해준다.

 

처음에 메모리 제한을 보지않고 그냥 풀어서 메모리 초과가 발생했다.

 

DP는 정말 풀어도 어려운 문제가 끝이 없는 것 같다.

실버1문제임에도 하루종일 고민해도 못풀어서 결국 다른 블로그 글들을 참조해서 풀었다.

확실히 문제를 많이 풀어봐야 될 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.