728x90

 0. [c++] 백준  - 


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


 1. 풀이


숫자를 한자리씩 계단 수 규칙을 유지하며 증가시켜주자.


처음 시작은 0을 제외한 1~9를 seed로 cache가 쌓이게 된다.


시작이 다른 9개의 수이므로 중복은 발생하지 않고, 비트마스크를 활용하여 방문한 수를 저장해주었다.



 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
59
60
61
62
63
64
65
66
#include<iostream>
 
using namespace std;
 
const int INF = 1000000000;
int N;
int cache[101][10][1 << 10];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
 
    for (int i = 1; i < 10; i++) {
        cache[1][i][1 << i] = 1;
    }
 
    //for (int order = 2; order <= N; order++) {
    //    for (int num = 0; num < 10; num++) {
    //        for (int visited = 0; visited < (1 << 10); visited++) {
    //            if (num == 0) {
    //                cache[order][num][visited | (1 << num)] = (cache[order][num][visited | (1 << num)] + cache[order - 1][num + 1][visited]) % INF;
    //            }
    //            else if (num == 9) {
    //                cache[order][num][visited | (1 << num)] = (cache[order][num][visited | (1 << num)] + cache[order - 1][num - 1][visited]) % INF;
    //            }
    //            else {
    //                cache[order][num][visited | (1 << num)] = (cache[order][num][visited | (1 << num)] + cache[order - 1][num - 1][visited]) % INF;
    //                cache[order][num][visited | (1 << num)] = (cache[order][num][visited | (1 << num)] + cache[order - 1][num + 1][visited]) % INF;
    //            }
    //            
    //        }
    //    }
    //}
 
    for (int order = 1; order < N; order++) {
        for (int num = 0; num < 10; num++) {
            for (int visited = 0; visited < (1 << 10); visited++) {
                if (cache[order][num][visited] == 0)
                    continue;
                if (num == 0) {
                    cache[order + 1][1][visited | (1 << 1)] = (cache[order + 1][1][visited | (1 << 1)] + cache[order][num][visited]) % INF;
                }
                else if (num == 9) {
                    cache[order + 1][8][visited | (1 << 8)] = (cache[order + 1][8][visited | (1 << 8)] + cache[order][num][visited]) % INF;
                }
                else {
                    cache[order + 1][num + 1][visited | (1 << (num + 1))] = (cache[order + 1][num + 1][visited | (1 << (num + 1))] + cache[order][num][visited]) % INF;
                    cache[order + 1][num - 1][visited | (1 << (num - 1))] = (cache[order + 1][num - 1][visited | (1 << (num - 1))] + cache[order][num][visited]) % INF;
                }
 
            }
        }
    }
 
    int ret = 0;
 
    for (int i = 0; i < 10; i++) {
        ret = (ret + cache[N][i][(1 << 10) - 1]) % INF;
    }
 
    cout << ret << endl;
 
    return 0;
}
cs

 3. 참고




질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > |c++| normal' 카테고리의 다른 글

|c++| 백준 1002 - 터렛(수학, 두 원이 만나는 점의 개수)  (0) 2019.07.26
[c++] 백준 2342 - Dance Dance Revolution(dp, 메모이제이션)  (0) 2019.07.13
[c++]백준 1315 - RPG(메모이제이션, dp)  (0) 2019.07.12
[c++]백준 11062 - 카드 게임(dp, 메모이제이션)  (0) 2019.07.12
[c++] 백준 2618 - 경찰차(dp)  (0) 2019.07.11

+ Recent posts

티스토리툴바