[백준] 9095번: 1, 2, 3 더하기 [C++]

 

알고리즘 분류: 다이나믹 프로그래밍

문제 링크: https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

【 풀이 】

 

DP, 동적 계획법으로 해결 가능한 문제이다.

이 문제의 경우는 11개의 수만 대상으로 하기에, 규칙만 제대로 찾아내면 시간제한 혹은 메모리 제한에 걸릴 일은 없다.

 

처음에는 1, 2, 3으로 나타낼 수 있는 모든 경우의 수를 구하면서 규칙을 알아내려 했지만, 5가 넘어가면서 직접 경우의 수를 계산하기에는 그 수가 너무 많아졌다.

그래서 예제에 있는 답안을 토대로 구해보았다.

정수 n이 주어졌을 때 n을 1, 2, 3의 합으로 나타내는 방법의 수를 담은 배열을 N이라고 하면 N[n]은 다음과 같다.

 

• N[1] = 1
• N[2] = 2
• N[3] = 4
• N[4] = 7
• N[7] = 44
• N[10]  = 274

1	2	3	4	5	6	7	8	9	10
1	2	4	7	?	?	44	?	?	274

여기서, N[4] = N[1] + N[2] + N[3] = 7 이다. 이것만 미루어 보았을 때 점화식은

 

N[1] = 1, N[2] = 2, N[3] = 4이고,

N[n] = N[n-3] + N[n-2] + N[n-1]

 

이라고 볼 수 있다. 이 점화식이 맞는지 검증해 보면

 

• N[5] = N[2] + N[3] + N[4] = 2 + 4+ 7 = 13
• N[6] = N[3] + N[4] + N[5] = 4 + 7 + 13 = 24
• N[7] = N[4] + N[5] + N[6] = 7 + 13 + 24 = 44

N[7]은 44로, N[n] = N[n-3] + N[n-2] + N[n-1] 은 이 문제의 점화식으로 볼 수 있다.

그리고 이 식을 토대로 Bottom-Up으로 구현했다.

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int n[12];
int main(void)
{
	n[1] = 1; n[2] = 2, n[3] = 4;
	int t;
	cin >> t;
    
	for (int i = 4; i < 12; i++)
		n[i] = n[i - 3] + n[i - 2] + n[i - 1];
        
	for (int i = 0; i < t; i++)
	{
		int num;
		cin >> num;
		cout << n[num] << '\n';
	}
	return 0;
}