백준 15990 - 1, 2, 3 더하기 5 (c++)

문제 출처 : https://www.acmicpc.net/problem/9095

 

<접근 방법>

Dp 이용

마지막 수가 1, 2, 3인 경우를 나누어서 저장

마지막 수가 1이면 앞에 2나 3이 와야 하고 2면 1이나 3, 3이면 1, 2가 와야 함

여기까지는 생각 해내는데 성공했지만, 도저히 점화식을 못 구하겠어서 다른 분들의 풀이를 참고했습니다.

 

<풀이>

	Dp[n][1]	dp[n][2]	dp[n][3]
n=1	1	0	0
n=2	0	1	0
n=3	1	1	1
n=4	2	0	1
n=5	1	2	1
n=6	3	3	2
n=7	5	2	2
n=8	4	5	3

숫자가 작으면 찾기 힘드니 n=8일 때를 확인해 보겠습니다.

dp[8][1]은 바로 위인 dp[7][2] + dp[7][3]에서 가져오면 되고

dp[8][2]는 그 위인 dp[6][1] + dp[6][3],

dp[8][3]은 또 그 위인 dp[5][2] + dp[5][3]에서 가져오면 됩니다. 

 

<점화식>

dp[n][1] = dp[n-1][2] + dp[n-1][3]

dp[n][2] = dp[n-2][1] + dp[n-2][3]

dp[n][3] = dp[n-3][1] + dp[n-3][2]

 

<소스 코드>

#include <iostream>
#define MAX 100001
#define VAL 1000000009
 
using namespace std;
 
int main() {
  int T, n;
  long long dp[MAX][4]={0};
 
  dp[1][1] = 1;
  dp[2][2] = 1;
  dp[3][1] = 1;
  dp[3][2] = 1;
  dp[3][3] = 1;
 
  for(int i=4; i<MAX; i++){
    dp[i][1] = (dp[i-1][2]+dp[i-1][3])%VAL;
    dp[i][2] = (dp[i-2][1]+dp[i-2][3])%VAL;
    dp[i][3] = (dp[i-3][1]+dp[i-3][2])%VAL;
  }
  
  cin >> T;
  while(T--){
    cin >> n;
    cout << (dp[n][1]+dp[n][2]+dp[n][3])%VAL << "\n";
  }
}

'마지막 수가 1이면 앞에 2나 3이 와야 한다.' 까지는 잘 접근했는데 n-1만 이용해서 값을 찾으려 하다가 시간을 많이 날렸네요... 이 풀이 방식에 접근하기까지 이미 많은 시간을 투자했기에 다른 사람들의 풀이를 봤는데 하루 정도만 더 고민해 볼 걸 싶기도 하고 조금 아쉽네요.

많은 사람이 그렇듯 저도 dp문제를 어려워합니다. 그래서 최근 dp문제를 좀 많이 풀어보고 있는데 그래도 거의 정답까지 근접했다는 것에 만족하며 복습 겸 코드와 풀이를 정리해서 올립니다.