[DP] [BOJ 9095] 1, 2, 3 더하기

 

9095번: 1, 2, 3 더하기

문제

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 방법 구하기

예시)

4 = 1 + 1 + 1 + 1

   = 1 + 1 + 2

   = 1 + 2 + 1

   = 2 + 1 + 1

   = 2 + 2

   = 1 + 3

   = 3 + 1

 

(7가지)

 

무식하게 접근하기

우선 무식하게 접근하고 패턴을 찾아보자고 생각하고 풀었는데 , 숫자를 모두 나열해보면서 Bottom-Up으로

찾아보려고 했는데, 규칙은 보였지만 명확하게 이해가 되지 않았다. 그래서 Top-Down 방식으로 그림을 그려봤다.

 

4를 1, 2, 3으로 더하여 표현하는 방법의 수

그림을 설명하자면, 4를 1, 2, 3으로 더하는 방법은 반대로 4에서 부터 시작해서 1, 2, 3을 빼가면서 나오는 0의 개수로도

생각할 수 있다. 따라서 4에서 1, 2, 3을 빼고, 그렇게 나온 수에서 다시 1, 2, 3을 빼는 것을 반복하여 0의 개수를 세면 답을 구할 수 있다.

 

하지만 위와 같은 그래프를 그리면 시간복잡도가 $O(3^N)$ 정도가 나오게 된다. (그래프의 깊이가 증가할수록 노드의 수가 3배로 증가하기 때문이다.) 물론 여기선 N <= 11이므로 문제를 풀 수 있겠지만, 좀더 효율적으로 풀어보자.

 

중복되는 부분 문제

 

위의 트리를 때, 4가 자식 중  0의 개수는 4 - 1, 4 - 2, 4 - 3, 즉 3, 2, 1 의 자식인 0의 개수를 모두 더한 것과 같다.

마찬가지로 임의의 N에 대하여 트리를 그려도 동일하게 N - 1, N - 2, N - 3의 0의 개수를 더한 것과 같다. 따라서

DP를 풀기 위한 조건이 성립한다. 따라서 다음 점화식을 세울 수 있다. $a_n = a_{n-1} + a_{n-2} + a_{n-3}$