[BOJ][C++] 백준 9095번 1, 2, 3 더하기
Updated:
9095번 1, 2, 3 더하기
1. 문제 정보
백준 온라인 저지 [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보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력1
3
4
7
10
예제 출력1
7
44
274
시간 / 메모리 제한
1초 / 128MB
2. 생각
-
주어진 문제 n을 나타내는 방법의 수를 쪼개어 n-1, n-2, n-3 … 1 작은 문제로 만들 수 있습니다.
또, 작은 문제의 해답을 합쳐 큰 문제를 풀 수 있으므로 다이나믹프로그래밍 방법으로 문제를 풀겠습니다. - 가장 마지막에 어떤 숫자를 더할 수 있는지 경우의 수를 생각해보는 방법으로 Bottom-up 방식으로 풀겠습니다.
dp배열은 각 원소에 해달하는 정수를 1, 2, 3의 합으로 나타내는 방법의 수를 저장합니다.0 0 1 1 0+1 1 2 1+1 0+2 2 3 1+1+1 2+1 1+2 0+3 4 4 1+1+1+1 2+1+1 1+2+1 3+1 1+1+2 2+2 1+3 7 - n번째 정수를 1, 2, 3의 합으로 나타내는 경우는 3가지가 있습니다.
1) 1을 더하는 경우 -> dp[n-1]의 방법의 수에 각각 1을 더합니다.
2) 2를 더하는 경우 -> dp[n-2]의 방법의 수에 각각 2를 더합니다.
3) 3을 더하는 경우 -> dp[n-3]의 방법의 수에 각각 3을 더합니다.
1), 2), 3)의 경우를 모두 더해야 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구할 수 있습니다. 따라서, dp[n] = dp[n-1] + dp[n-2] + dp[n-3]의 점화식을 도출할 수 있습니다.
- dp[0], dp[1], dp[2]의 경우는 일반항으로 초기값을 정해줍니다. i=3부터 반복문을 통해 구할 수 있습니다.
dp[0]을 1로 초기화한 이유는 dp[3]의 경우에서 0+3도 3의 합으로 표현할 수 있기 때문에 1가지로 세도록 1로 초기화했습니다.
3. 소스코드 (C++)
