![[백준 1562] 계단 수 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcujmJJ%2Fbtq8ppYMvnw%2FkMZTamlKylrsLxarYkgJr0%2Fimg.png)
1562번: 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
비트필드를 이용한 다이나믹 프로그래밍
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;
}
|
cs |
'Algorithm > BOJ' 카테고리의 다른 글
| [백준 2636] 치즈 C++ (0) | 2021.07.01 |
|---|---|
| [백준 4196] 도미노 C++ (0) | 2021.07.01 |
| [백준 2623] 음악프로그램 C++ (0) | 2021.06.29 |
| [백준 11266] 단절점 C++ (0) | 2021.06.27 |
| [백준 1208] 부분수열의 합2 C++ (0) | 2021.06.27 |