본문 바로가기
Algorithm Theory/Dynamic Programming

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

by hyeyoo 2020. 3. 18.
※ 이 블로그의 글은 글쓴이가 공부하면서 정리하여 쓴 글입니다.
※ 최대한 내용을 검토하면서 글을 쓰지만 틀린 내용이 있을 수 있습니다.
※ 만약 틀린 부분이 있다면 댓글로 알려주세요.

 

 

9095번: 1, 2, 3 더하기

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각

www.acmicpc.net

문제

정수 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}$

 

 

댓글