알고리즘 :: 백준 :: DP :: 15990 :: 1, 2, 3 더하기 5

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.
1+2+1
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

문제접근

1. https://velog.io/@embeddedjune/알고리즘-백준-DP-9095-1-2-3-구하기 의 심화된 문제다.
2. 이전 문제에서는 간단히 점화식을 구해서 세 부분문제를 더해주는 것으로 문제를 해결할 수 있었지만, 이번에는 연속된 수가 와서는 안되므로 점화식의 형태가 달라진다.
3. 문제의 핵심은 마지막에 오는 수가 무엇이냐에 따라 답이 달라진다라는 것이다.
4. 예를 들어, 숫자 N을 1, 2, 3으로 표현할 때, □□□...■ 에서
   i) ■이 1이라면 -> ■ 앞의 수는 2 또는 3만 올 수 있다.
   ii) ■이 2라면 -> ■ 앞의 수는 1 또는 3만 올 수 있다.
   iii) ■이 3이라면 -> ■ 앞의 수는 1 또는 3만 올 수 있다.
5. 2차원 메모이제이션을 사용해서 $D(n, L)$을 n을 표현할 때 마지막에 오는 수가 L인 경우라고 생각하자. (중요!!)
6. 따라서 점화식은, $D(n, 1) +D(n,2)+D(n,3)$이고,
   $if\ (n==1)\ \ return \ \ 1,\ \ D(n, 1) = D(n-1,2)+D(n-1,3)$
   $if\ (n==2)\ \ return \ \ 1,\ \ D(n, 2) = D(n-1,1)+D(n-1,3)$
   $if\ (n==3)\ \ return \ \ 1,\ \ D(n, 3) = D(n-1,1)+D(n-1,2)$이다.

코드

#include <iostream>
#include <cstring>
using namespace std;

static constexpr long long Mod = 1000000009LL;
static long long dp[100001][4];
static int T;

// 계산 과정에서 큰 수가 나올 수 있으므로 long long 자료형 사용, int 쓰면 틀린다.
long long solve(int num, int endCard) {
    if (num <= 0) return 0;			// 기저1 :: num이 0보다 작거나 같은 음수라면 경우의 수 0
    if (num == endCard) return 1;	// 기저2 :: num == endCard면 경우의 수 1
    if (dp[num][endCard] > 0) return dp[num][endCard];	// 중복 연산 X
	
	// 마지막 숫자가 1이면 그 이전 숫자는 2 또는 3이어야 한다. 
    if (endCard == 1)  dp[num][endCard] = (solve(num - 1, 2) + solve(num - 1, 3)) % Mod;
    else if (endCard == 2) dp[num][endCard] = (solve(num - 2, 1) + solve(num - 2, 3)) % Mod;
    else if (endCard == 3) dp[num][endCard] = (solve(num - 3, 1) + solve(num - 3, 2)) % Mod;
    
    return dp[num][endCard];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    memset(dp, 0, sizeof(dp));
    while (T--) {
        int n = 0;  cin >> n;
        cout << (solve(n, 1) + solve(n, 2) + solve(n, 3)) % Mod << '\n';
    }
}

결과