취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9095번 문제인 1, 2, 3 더하기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/9095 

1, 2, 3은 각각 아래와 같이 표현이 가능하다:

1(1가지): 1

2(2가지): 2, 1+1

3(4가지): 3, 1+2, 2+1, 1+1+1

4 이상의 자연수 n에 대하여, n을 1과 2와 3의 합으로 나타낸 표현은 "+1"로 끝나거나 "+2"로 끝나거나 "+3"으로 끝난다는 점을 관찰하자. "+1"로 끝나는 표현의 개수는 n-1을 1과 2와 3의 합으로 나타내는 가짓수와 같고, "+2"로 끝나는 표현의 개수는 n-2를 1과 2와 3의 합으로 나타내는 가짓수와 같고, "+3"으로 끝나는 표현의 개수는 n-3을 1과 2와 3의 합으로 나타내는 가짓수와 같다. 이를 이용해 점화식을 세울 수 있고, 문제를 해결할 수 있다.

아래는 제출한 소스코드이다:

#include <iostream>
using namespace std;

int ans[11];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ans[1] = 1, ans[2] = 2, ans[3] = 4;
	for (int i = 4; i < 11; i++) {
		ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
	}

	int T; cin >> T;
	while (T--) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	}
}