[백준/C++] 15990번_1,2,3 더하기 5

문제는 다음과 같습니다.

다른 1, 2, 3더하기 문제와 비슷하지만,
핵심은 다음과 같습니다.

단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

이 핵심을 정리하면 다음과 같습니다.

• 1 앞에는 2, 3만 올 수 있다.
• 2 앞에는 1, 3만 올 수 있다.
• 3 앞에는 1, 2만 올 수 있다.

즉 어떤수 n을 1, 2, 3의 합으로 나타내는 경우의 수를 구할 때
가장 마지막 수가 i(i=1, 2, 3)라 했을 때

경우의 수는 = d[n][1]+d[n][2]+d[n][3] 의 합으로 나타낼 수 있습니다.

그리고 각각의 d[n][1], d[n][2], d[n][3]은 앞에 자신의 수와 다른 수가 와야하므로 다음과 같이 구할 수 있습니다.

• d[n][1] = d[n-1][2]+d[n-1][3]
• d[n][2] = d[n-2][1]+d[n-2][3]
• d[n][3] = d[n-3][1]+d[n-3][2]

다음 그림과 같이 진행된다고 보면 됩니다!

제 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

long long dp[100001][4]={0, };
long long MOD = 1000000009;

void func(void){
  dp[1][1]=dp[2][2]=dp[3][1]=dp[3][2]=dp[3][3]=1;

  for(int i=4; i<=100000; i++){
    dp[i][1]=(dp[i-1][2]+dp[i-1][3]) % MOD;
    dp[i][2]=(dp[i-2][1]+dp[i-2][3]) % MOD;
    dp[i][3]=(dp[i-3][2]+dp[i-3][1]) % MOD;
  }

}


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

    int n, tmp;
    long long res;
    func();
    cin>>n;
    for(int i=0; i<n; i++){
      cin>>tmp;
      res=(dp[tmp][1]+dp[tmp][2]+dp[tmp][3])%MOD;
      cout<<res<<endl;
    }
    
    return 0;
}

2월 5일 토요일 복습)

#include <bits/stdc++.h>
using namespace std;

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

    long long dp[100001][4]={0, };
    long long mod = 1000000009;
    dp[1][1]=1;
    dp[2][2]=1;
    dp[3][1]=1; dp[3][2]=1; dp[3][3]=1;
    int n, tmp; cin>>n;

    for(int i=4; i<=100000; i++){
        dp[i][1]=(dp[i-1][2]+dp[i-1][3])%mod;
        dp[i][2]=(dp[i-2][1]+dp[i-2][3])%mod;
        dp[i][3]=(dp[i-3][1]+dp[i-3][2])%mod;
    }

    for(int i=0; i<n; i++){
      cin>>tmp;
      cout<<(dp[tmp][1]+dp[tmp][2]+dp[tmp][3])%mod<<"\n";
    }

    return 0;
}