본문 바로가기
백준/C++

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

by 대니스 2022. 9. 1.

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

 

9095번: 1, 2, 3 더하기

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

www.acmicpc.net

소스 코드 : 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	int T;
	cin >> T;
	vector<int> v(13);

	v[1] = 1;
	v[2] = 2;
	v[3] = 4;

	for (int i = 4; i <= 12; i++)
		v[i] = v[i - 3] + v[i - 2] + v[i - 1];

	while (T != 0)
	{
		int num;
		cin >> num;
		cout << v[num] << '\n';
		T--;
	}
}

마무리 : 계산 문제로 먼저 dp로 풀 수 있을지 확인을 해보았는데 예상대로 dp로 풀어서 답을 맞출 수 있게 되었다. dp를 잘 모르는 사람이라면 문제를 풀기 어려웠을 것이다.