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

문제 출처: www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

1. 코드

#include <iostream>

using namespace std;

int main(void)
{
	int t;
	int n;
	int arr[11] = { 1, 1, 2 };

	cin >> t;
	for (int i = 3; i < 11; i++)
		arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];

	for (int i = 0; i < t; i++)
	{
		cin >> n;
		cout << arr[n] << endl;
	}
	return 0;
}

(실행)

2. 풀이

먼저, 이 문제는 점화식을 풀면 쉽게 풀 수 있다. 그리고 n의 크기가 11 미만이기 때문에 배열의 크기를 11로 해주고, arr 배열의 11 인덱스 값까지 먼저 전부 구해주고 입력한 n의 값을 출력해준다.

점화식은 저 같은 경우 직접 그려서 수를 확인해보면 n의 값이 1부터 1, 2, 4, 7, 13, 24, 44... 이러한 형태로 증가하는데 자세히 보면 f(n) = f(n - 1) + f(n - 2) + f(n - 3)이 성립된다. 이렇게 점화식을 구했다면 n이 0~2까지의 초기값을 설정해주고, 그다음에 3부터 차례대로 구하면 된다.

3. 느낀 점

점화식을 찾을 때 직접 그리지않고 찾는 방법을 알고 싶다. 그리는 것이 쉽게 알아볼 수는 있지만 그리는 과정이 고된 작업이다.