백준 9095 풀이

링크텍스트

1,2,3으로 정해진 숫자를 구하는 문제이다.

오랜만에 쉽다고 해야하나 간단하게 풀리는 문제를 만나 편했다.

4는 문제 예시로 있으니 넘어가고 5를 예시로 하자면
5는 1+4,2+3,3+2,4+1일 수 있다.

즉 4를 구하는 경우의 수 + 3을 구하는 경우의 수 + 2를 구하는 경우의 수로 구할 수 있다.

즉 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]과 같다.

점화식을 구했다면 답은 쉽게 나온다.

문제의 핵심은 현재 숫자는 이전의 수에 +1,+2,+3을 한 것과 같다는 것을 빠르게 눈치채는 것이다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int n;
int m;
bool visited[9] = { 0, };
int arr[11];
int* nums;

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

	int answer = 0;

	cin >> n;
	nums = new int[n];
	
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;

	for (int i = 4; i <= 10; i++) {
		arr[i] = arr[i - 2] + arr[i - 1] + arr[i - 3];
	}

	for (int i = 0; i < n; i++) {
		int tmp = nums[i];
		cout << arr[tmp] << '\n';
	}

	return 0;
}