[BOJ] 백준 9095번 : 1, 2, 3 더하기 (JAVA)

문제

정수 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보다 작다.

 

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

풀이

다이나믹 프로그래밍으로 해결할 수 있는 문제였습니다.

 

 

특정 수 N을 1, 2, 3의 합으로 표현할 수 있는 경우의 수를 구하는 것이 핵심입니다.

 

가령,  N = 1일 때는 1로만 표현가능하므로 경우의 수가 1가지이고, N = 2일 때는 1 + 1 또는 2로 표현가능하므로 경우의 수가 2가지이고, N = 3일 때는 1 + 1 + 1, 1 + 2, 2 + 1, 3으로 표현가능하므로 경우의 수가 4가지입니다.

 

물론, 위와 같이 전부 나열하면서 알 수도 있겠지만 좀 더 똑똑하게 N = 4부터 경우의 수를 구해봅시다.

 

 

N = 4일 때, 1, 2, 3으로 표현할 수 있는 경우는 크게 보면 1 + 3, 2 + 2, 3 + 1입니다.

 

N = 5일 때, 1, 2, 3으로 표현할 수 있는 경우는 크게 보면 2 + 3, 3 + 2, 4 + 1입니다.

 

 

즉, N = i일 때, 1, 2, 3으로 표현할 수 있는 경우는 크게 보면 i - 3 + 3, i - 2 + 2, i - 1 + 1이므로 우리는 N = i - 3, i - 2, i - 1일 때의 경우의 수를 모두 더하면 i일 때의 경우의 수를 얻어낼 수있습니다.

 

따라서, 점화식으로는 dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1] 이라는 것을 알 수 있습니다.

 

위 식을 이용하여 bottom-up 코드를 작성하면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.