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

문제 주소 : https://www.acmicpc.net/problem/9095

 

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

-> 이유는 ( 3^10​ + 3^9 + ... + 3^1) 의 계산을 하게 되면, 시간 초과가 발생한다.

 

(2) 동작 방식

​

- num을 n부터 1, 2, 3으로 빼면서 함수를 실행시켜나간다.

- 0에 도착하는 경우의 모든 수를 세야 한다.

- num - 1, num - 2, num - 3을 하는 경우가 있으므로 이 3 경우를 전부 합쳐주면 된다.

​

(3) 다이나믹 프로그래밍은 대부분 결과 출력값 = 메모이제이션 테이블 = 함수반환 값이다. 즉, 재귀 함수를 호출할 때 넘겨주는 그 매개변수 값이 함수(num - 1)의 의미는 num - 1의 숫자를 1, 2, 3 으로 만들 수 있는 총 경우의 수에서 1을 포함해서 만드는 경우의 수와 같다

​

(4) 문제를 파악한 후에 그에 맞는 메모이제이션 테이블 (아래 dp행렬)의 정의를 내려줘야한다. 그 정의에 맞는 함수 내 알고리즘을 구현해야 한다.

​

2. Source Code

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define MAX 11
using namespace std;
// dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법
int dp[MAX];
int ans[MAX];
int t, n;

// 코드 알고리즘 순서
/*
	1. num을 n부터 1, 2, 3으로 빼면서 함수를 실행시켜나간다.
	2. 0에 도착하는 경우의 모든 수를 세야 한다.
	3. num - 1, num - 2, num - 3을 하는 경우가 있으므로 이 3 경우를 전부 합쳐주면 된다.
*/

int solution(int num)
{
	if (num == 0) return 1;

	int& result = dp[num];
	if (result != -1)
		return result;

	result = 0;
	return result = solution(num - 1) + solution(num - 2) + solution(num - 3);
}

int main()
{
	cin >> t;
	for (int i = 1; i < 11; i++)
	{
		memset(dp, -1, sizeof(dp));
		ans[i] = solution(i);
	}
		
	
	while (t--)
	{
		cin >> n;
		cout << ans[n] << endl;
	}

	return 0;
}