[백준] 9095번 - 1, 2, 3 더하기

www.acmicpc.net

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

문제

💡

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1

1+1+2

1+2+1

2+1+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

시간 제한: 1초

메모리 제한: 512MB

입력

💡

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

💡

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력	예제 출력
3 4 7 10	7 44 274

풀이

테스트 케이스의 출력을 보면 규칙을 찾을 수 있다. n = (n-3) + (n-2) + (n-1)

이 규칙을 가지고 DP table을 구현하면 빠르게 답을 구할 수 있다.

dp[n]이 계산이 되어있다면 테이블에서 값을 출력하고, 계산이 안되어있으면 재귀를 통해 구한 후 테이블에 저장한다.

코드


#include <iostream>
#include <vector>
using namespace std;

int sumcase(int n, vector<int>& dp) {
	if (dp[n] != -1) {
		return dp[n];
	}
	dp[n] = sumcase(n - 1, dp) + sumcase(n - 2, dp) + sumcase(n - 3, dp);
	return dp[n];
}

int main() {
	int t,n;
	cin >> t;
	vector<int> inputs(t);
	for (int i = 0; i < t; ++i) {
		cin >> inputs[i];
	}

	vector<int> dp(11, -1);
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 4;

	for (auto i : inputs) { 
		cout << sumcase(i - 1, dp) << "\n";
	}

	return 0;
}