15989 1, 2, 3 더하기 4

15989 1, 2, 3 더하기 4 / c++ / Gold5 / 1시간+

문제 및 코드

풀이 과정

동적 프로그래밍

1. N개의 수가 주어질 때, 그 수를 1,2,3의 합으로 만들 수 있는 경우의 수를 출력하는 문제 (단, 순서만 바뀐 경우는 같은 것으로 친다.)
2. 결국 i를 1,2,3으로 더한 경우의 수는 아래와 같이 나눠진다.
   1. 다른 수에서 1을 더한 경우
   2. 다른 수에서 2를 더한 경우
   3. 다른 수에서 3을 더한 경우
3. 다른 수에서 3을 더해 i라는 값을 만들려면 당연히 i-3에서 3을 더해야한다. 즉, 위의 경우를 다시 정리하면 아래와 같다.
   1. i-1 에서 1을 더한 경우
   2. i-2 에서 2를 더한 경우
   3. i-3 에서 3을 더한 경우
4. 예를 들어 8을 만들기 위해 8-2인 6에서 2를 더한다고 가정해보자, 이 때, 6의 모든 식에 2를 더한다면 (3 + 3) + 2 라는 식도 그 중에 존재하게 된다. 하지만 이는 8-3인 5에서 3을 더할 때 존재하는, (3 + 2) + 3 이라는 식과 순서만 다를 뿐, 동일한 식이다.
5. 따라서 여기서는 중복을 피하기 위해 DP[i][j]는, i라는 수를 만들기 위해, 최대 j까지만 사용한 경우의 수를 뜻한다. (DP[4][2]는 4를 만들 때 2까지만 사용한 경우, 2 + 2, 2 + 1 + 1)
6. 이렇게 나눠 놓으면, DP[8][2]는 8을 만들기 위해 6을 만드는 경우의 수에 2를 더하지만, 마찬가지로 6에서도 최대 2까지만 사용한 값에 2를 더하기 때문에 위와 같은 중복이 발생하지 않는다.
7. 여기까지 적용하면 3번의 경우를 다시 아래와 같이 정리할 수 있다.
   1. DP[i-1][1] 에 1을 더한 경우
   2. DP[i-2][1] 에 2를 더한 경우와 DP[i-2][2] 에 2를 더한 경우의 합
   3. DP[i-3][1] 에 3을 더한 경우와 DP[i-3][2] 에 3을 더한 경우와 DP[i-3][3]에 3을 더한 경우의 합
8. 위의 식을 정리하면
   1. i를 1,2,3의 합으로 만드는 경우의 수는 DP[i][1] + DP[i][2] + DP[i][3] 이다.
   2. DP[i][1] = 1 이다. (모든 수가 1로만 이루어진 식)
   3. DP[i][2] = DP[i-2][1] + DP[i-2][2] 이다. (이전 값의 1과 2로 구성된 식들에 2를 더한 경우)
   4. DP[i][3] = DP[i-3][1] + DP[i-3][2] + DP[i-3][3] 이다. (즉, i-3을 만들 수 있는 모든 경우의 수와 같다.)
9. N개의 Input을 받아서 DP[Input][1] + DP[Input][2] + DP[Input][3]을 출력
10. 해결

회고

1. 처음부터 중복이 문제가 될거라는 부분은 인지하고 있었는데, 그 중복을 어떻게 잡을지가 떠오르지 않았다.
2. 결국 1시간을 넘겨서 다른 분들의 풀이를 봤는데, 위와 같이 경우를 +1, +2, +3으로 나누고, 각각 1까지만, 2까지만, 3까지 다 사용한 식으로 나눠서 계산하면 중복을 제거할 수 있다는 사실을 알게 되었다.
3. 시간을 많이 소모했지만 또 하나의 문제 유형을 알게 됐다. 다음에는 비슷한 문제가 나오면 저렇게 경우를 나눠서 생각해봐야겠다.