[BOJ] 9095 1,2,3 더하기(다이나믹 프로그래밍)

1. 문제

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

2. 아이디어

3. 풀이 과정

1) ⭕RIGHT⭕ - 반복문 이용

• 코드

#include <iostream>
using namespace std;

int addition[11] = { 0,1,2,4};

int solve(int n)
{
	if (addition[n]) return addition[n];
	else return addition[n] = solve(n - 1) + solve(n - 2) + solve(n - 3);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T; // Testcase 수
	int n;

	cin >> T;

	solve(10); // 가능한 모든 n에 대해서 미리 구하여둠
	while (T--)
	{
		cin >> n;
		cout << addition[n] << '\n';
	}
	return 0;
}

• 추가 설명
  - addition 배열이 11까지인 이유
  n의 범위가 1이상 10이하의 정수이기 때문
  0을 더하는 방법 수 0가지
  1을 더하는 방법 수 1가지
  2를 더하는 방법 수 2가지
  3을 더하는 방법 수 4가지
  ...
  n을 더하는 방법수 addition[n]가지
  

2) ⭕RIGHT⭕ - 재귀 이용

• 코드

#include <iostream>
using namespace std;

int DP[12] = { 0 };

int recursive(int i) {
	if (i == 1) return 1;
	if (i == 2) return 2;
	if (i == 3) return 4;
	DP[i] = recursive(i - 1) + recursive(i - 2) + recursive(i - 3);

	return DP[i];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int testcase; cin >> testcase;
	int max_prev_n = 3, cur_n;

	DP[0] = 0;
	DP[1] = 1; DP[2] = 2; DP[3] = 4;

	while (testcase--) {
		cin >> cur_n;
		
		if (max_prev_n < cur_n) recursive(cur_n);

		cout << DP[cur_n] << '\n';

		if (max_prev_n < cur_n) max_prev_n = cur_n;
	}
	return 0;
}

• 추가 설명
  • if (max_prev_n < cur_n)
    주어진 여러 번의 테스트케이스에서 이미 구한 적이 있다면 재귀적인 계산을 하지 않고 바로 결과를 출력한다.
    (ex. 테스트케이스가 7,4,10 순서로 주어진다면 4인 경우 재귀적인 계산을 하지 않는다)