[210416][백준/BOJ] 9095번 1, 2, 3 더하기

문제

입출력

---

풀이

4를 1, 2, 3의 합으로 나타내는 방법은
1+1+1+1
1+2+1
2+1+1
3+1
1+1+2
2+2
1+3
총 7가지가 있다.

각 방법의 맨 뒤를 보면 +1, +2, +3이 보인다. 이를 제외하고 보면
3을 1,2,3의 합으로 나타내는 1+1+1, 1+2, 2+1 3
2를 1,2,3의 합으로 나타내는 1+1, 2
1을 1의 합으로 나타내는 1 로 나타낼 수 있다.

즉 d(1)+1, d(2)+2, d(3)+3 으로 나타낼 수 있다.
따라서 이를 점화식으로 나타내면 d(n) = d(n-1) + d(n-2) + d(n-3)이며 초기값은 d(1)=1, d(2)=2, d(3)=4이다.

코드

top-down 방식

#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 4;
	if (d[n] != 0) return d[n];

	d[n] = dp(n - 1) + dp(n - 2) + dp(n - 3);
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n;
		cin >> n;
		cout << dp(n) << '\n';
	}
}

bottom-up 방식

#include <bits/stdc++.h>
using namespace std;

int d[102];

int dp(int n)
{
	d[1] = 1; // 1+3
	d[2] = 2; // 1+1+2, 2+2
	d[3] = 4; // 1+1+1+1, 1+2+1. 2+1+1, 3+1 

	for (int i = 4; i <= n; ++i)
		d[i] = d[i - 1] + d[i - 2] + d[i - 3];
	return d[n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;

	while (tc--)
	{
		int n;
		cin >> n;
		cout << dp(n) << '\n';
	}
}