문제
정수 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을 빼가면서 나오는 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}$
'Algorithm Theory > Dynamic Programming' 카테고리의 다른 글
[DP] [BOJ 1149] RGB거리 (0) | 2020.03.20 |
---|---|
[DP] [BOJ 11726] 2 x n 타일링 (0) | 2020.03.19 |
[DP] [BOJ 1463] 1로 만들기 (0) | 2020.03.18 |
DP 백준 문제 풀이 (0) | 2020.03.18 |
동적 프로그래밍(Dynamic Programming)의 개념 (0) | 2019.10.07 |
댓글