[백준] 15990번 1, 2, 3 더하기 5 (C++) - dynamic programming

문제

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

15990번: 1, 2, 3 더하기 5

코드

#include <iostream>

using namespace std;
long long dp[100001][3] = {{0,0,0},{1,0,0},{0,1,0},{1,1,1}};
long long sum[100001] = {0,1,1,3};

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

  int t;
  cin >> t;

  for(int i=0; i<t; i++){
    int n;
    cin >> n;
    if(dp[n][0] == 0 && dp[n][1] == 0 && dp[n][2] == 0){
      for(int j=4; j<=n; j++){
        dp[j][0] = (dp[j-1][1] + dp[j-1][2])%1000000009;
        dp[j][1] = (dp[j-2][0] + dp[j-2][2])%1000000009;
        dp[j][2] = (dp[j-3][0] + dp[j-3][1])%1000000009;
        sum[j] = (dp[j][0] + dp[j][1] + dp[j][2])%1000000009;
      }
    }
    cout << sum[n] << '\n';
  }
  return 0;
}

정리

dynamic programming 문제다. 우선 이 문제를 풀기 위해 경우의 수를 쭉 나열해 보았서 특정한 규칙이 있는지 찾아보았다.

 

n=1 → 1

n=2 → 2

n=3 → 2+1 | 1+2, 3

n=4 → 2+1+1 | 1+2+1 | 3+1 | 2+2 | 1+3 → 1+2+1 | 3+1 | 1+3

 

n=4일때 값을 구하기 위해서는 n=3일때 경우의 수들에 +1을 한 경우들(2+1+1, 1+2+1, 3+1)과 n=2일때 경우의 수들에 +2를 한 경우들(2+2)과 n=3일때 경우의 수들에 +3한 경우(1+3)들 중에 같은 수가 연속으로 나오는 경우를 제외하면 된다. 그럼 1+2+1, 3+1, 1+3의 경우만 남는다.

 

n=1 → 1                      (끝자리가 3인 경우는 세지 않는다)

n=2 → 2                      (끝자리가 2인 경우는 세지 않는다)

n=3 → 2+1, 1+2, 3         (끝자리가 1인 경우는 세지 않는다)

n=4 → 1+2+1, 3+1, 1+3

 

그럼 여기서 알 수 있다

n=4를 구하기 위해

n=3일 때 경우의 수들에서 끝자리가 1인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=2일 때 경우의 수들에서 끝자리가 2인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=1일 때 경우의 수들에서 끝자리가 3인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

 

한 번만 더 해보자

 

n=2 → 2                         (끝자리가 3인 경우는 세지 않는다)

n=3 → 2+1, 1+2, 3            (끝자리가 2인 경우는 세지 않는다)

n=4 → 1+2+1, 3+1, 1+3     (끝자리가 1인 경우는 세지 않는다)

n=5 → 1+3+1, 2+1+2, 3+2, 2+3

 

n=5를 구하기 위해

n=4일 때 경우의 수들에서 끝자리가 1인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=3일 때 경우의 수들에서 끝자리가 2인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=2일 때 경우의 수들에서 끝자리가 3인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

 

...

 

그럼 여기서 점화식을 구할 수 있는데

n=j를 구하기 위해

n=j-1일 때 경우의 수들에서 끝자리가 1인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=j-2일 때 경우의 수들에서 끝자리가 2인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

n=j-3일 때 경우의 수들에서 끝자리가 3인 경우에는 같은 수가 연속으로 두 번 나오기 때문에 이 경우는 세지 않는다.

 

즉 이말은 다음과 같다.

n=j-1일 때 경우의 수들에서 끝자리가 2인 경우와 3인 경우만 센다.

n=j-2일 때 경우의 수들에서 끝자리가 1인 경우와 3인 경우만 센다.

n=j-3일 때 경우의 수들에서 끝자리가 1인 경우와 2인 경우만 센다.

 

그래서 다음과 같은 점화식을 도출해낼 수 있다.

dp[j][0] = dp[j-1][1] + dp[j-1][2]
dp[j][1] = dp[j-2][0] + dp[j-2][2]
dp[j][2] = dp[j-3][0] + dp[j-3][1]

참조