[백준 1562] 계단 수 C++

1562번: 계단 수

비트필드를 이용한 다이나믹 프로그래밍

---

1. 문제 해결 아이디어

 

현재 구한 계단 수의 자릿수, 마지막 숫자

위 2개의 정보를 가지는 2차원 배열로 문제를 해결하려 했었는데 당연히 답이 제대로 나오지 않았다.

 

0~9의 숫자가 각각 사용되었는지 아닌지 알아야 하기 때문에 (10개의 숫자 각각 사용되었는지 아닌지에 대한 경우의 수 2^10)

따라서 [1 << 10] 배열을 추가해서 지금까지 어떤 숫자를 사용했는지 알 수 있게 했다.

 

마지막 숫자가 0인 경우는 이전 숫자가 1로 끝난 경우의 수를 그대로 받고, 9인 경우에는 이전 숫자가 8로 끝난 경우의 수를 그대로 받는다.

이외의 경우에는 i-1로 끝난 경우와 i+1로 끝난 경우의 수를 합친게 된다.

 

n개의 숫자가 방문했는지 아닌지를 쉽게 판단하기 위해서 비트필드를 사용하면 좋다.

 

비트필드가 싫다면 dp[n][i][1][1][1][1][1]....처럼 최대 자리수에 맞게 배열의 차원을 늘려줘도 될 것같다...

---

2. 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

#include <iostream>   #define MOD 1000000000 using namespace std;   int N, cmp, res; long long dp[101][10][1 << 10];   void solve(){          for(int i = 1; i <= 9; i++){         dp[1][i][1 << i] = 1;     }          for(int n = 2; n <= 100; n++){         for(int i = 0; i <= 9; i++){             for(int k = 0; k < (1 << 10); k++){                                  // k의 i번째 bit를 on 시킨다                 int offset = k | (1 << i);                                  // n자리 + i로 끝나고 + 기존 k 상태(여태 사용한 숫자의 모음)에서 숫자 i를 추가하는 경우는                 // n-1자리 + i-1 or i+1로 끝나고 + 기존 상태의 값(숫자 i를 추가하지 않음) 을 더해줘야 한다                 if(i == 0){                     dp[n][i][offset] = (dp[n][i][offset] + dp[n-1][1][k]) % MOD;                 }                 else if(i == 9){                     dp[n][i][offset] = (dp[n][i][offset] + dp[n-1][8][k]) % MOD;                 }                 else{                     dp[n][i][offset] = (dp[n][i][offset] + dp[n-1][i-1][k]) % MOD;                     dp[n][i][offset] = (dp[n][i][offset] + dp[n-1][i+1][k]) % MOD;                 }             }                                   }     }          int offset = 0;     long long ans = 0;     for(int i = 0; i <= 9; i++){         ans = (ans + dp[N][i][cmp]) % MOD;     }     cout << ans; }   int main(){     cin >> N;          for(int i = 0; i <= 9; i++){         cmp |= (1 << i);     }          solve();          return 0; } Colored by Color Scripter

cs