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

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

9095번: 1, 2, 3 더하기

 

dp 세번째 유형의 문제이다.

 

규칙을 찾기위해 경우의 수를 계산해 보았다.

 

dp[1] = 1                1가지

dp[2] = 1 + 1

            2                2가지

dp[3] = 1 + 1 + 1

            2 + 1

            1 + 2

            3                4가지

dp[4]는 문제에 나와있다.

 

dp[4]를 살펴보면 dp[1]에 경우의 수 가장 오른쪽에 3을 더하고

                            dp[2]에 경우의 수 가장 오른쪽에 2를 더하고

                            dp[3]에 경우의 수 가장 오른쪽에 1을 더하여 만들 수 있음을 알 수 있다.

 

설명이 어렵게 느껴진다면 2 x 1 타일 만들기 문제 (11726, 11727)를 풀어보고 오는것을 추천한다.

 

따라서 점화식은

 

dp[i] = dp[i-1] + dp[i-2] +dp[i-3] 으로 나타낼 수 있고 코드로 구현한다면

 

#include <iostream>
using namespace std;
 
int dp[1001] = { 0 };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	for (int test_case = 1; test_case <= t;test_case++) {
 
		int n;
		cin >> n;
 
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
 
		for (int i = 4;i <= n;i++) {
			dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]);
		}
 
		cout << dp[n] << "\n";
 
	}
	return 0;
}

 

이 문제는 2 + 1과 1 + 2를 다른 경우로 구분짓고 있지만 같은 경우로 구분짓는 경우는 어떻게 코드를 짜야할 지 고민이 된다.