[C++/Python] 백준 9095 - 1, 2, 3 더하기

문제 링크

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

9095번: 1, 2, 3 더하기

 

 

N이 1일 때는 1, 2일 때는 2, 3일 때는 4가지 방법이 있습니다.

 

N이 4일 때는

3일 때에서 1씩 더하는 방법

2일 때에서 2씩 더하는 방법

1일 때에서 3씩 더하는 방법이 총 방법의 수 입니다.

 

N이 5일 때도 마찬가지로

N이 2, 3, 4일 때의 방법의 합과 같습니다.

 

따라서 N이 4 이상일 때에는 dp(N-1) + dp(N-2) + dp(N-3) 으로 구할 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr);
	using namespace std;
	int d[11];
	int dp(int n){
	if(n==1) return 1;
	if(n==2) return 2;
	if(n==3) return 4;
	if(d[n]!=0) return d[n];
	return d[n] = dp(n-1) + dp(n-2) + dp(n-3);
	}
	int main(){
	fastio;
	int test_case,n;
	cin >> test_case;
	while(test_case--){
	cin >> n;
	cout << dp(n) << endl;
	}
	return 0;
	}

view raw 9095.cpp hosted with ❤ by GitHub

	test_case = int(input())
	d = []
	d.append(0)
	d.append(1)
	d.append(2)
	d.append(4)
	for i in range(4,11):
	d.append(d[i-1] + d[i-2] + d[i-3])
	for _ in range(test_case):
	n = int(input())
	print(d[n])

view raw 9095.py hosted with ❤ by GitHub