문제집


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


그래프가 유향 그래프라면, 노드 간에는 위상이 정해진다.


a노드에서 b노드로 진출하는 간선이 있다면, a와 b의 위상이 서로 다른 셈이다.



실생활에서 노드간의 위상은, 선수강과목이나 테크트리에서 찾아볼 수 있다.


넥서스가 있어야 게이트웨이를 지을수 있드시, 객체지향프로그래밍을 들어야 자료구조를 들을 수 있드시,


간선의 방향에 따라 노드간에 위상이 결정된다.



위상정렬은, 이와 같은 유향 그래프에서 노드 간의 위상을 순서대로 구하는 알고리즘이다.


따라서 유향그래프 내 사이클이 존재한다면, 즉 DAG이 아니라면 위상정렬할 수 없다.



여러가지 방법이 있지만, 주로 사용하는 진입차수를 이용한 풀이를 소개하고자 한다.


진입차수는 해당노드를 향한 간선의 개수를 뜻한다.


즉 1->3 // 2->3 의 간선이 있다면, 노드3의 진입차수는 2다.



위상정렬은 우선 모든 노드의 진입차수를 구하고 시작한다.


다음에는 진입차수가 0인 노드들을 전부 큐에 넣는다.


이제 큐에서 하나씩 꺼내면서 노드에서 나가는 간선들을 모두 제거한다.


현재 간선은 진입차수로 표현되었기 때문에, 진입차수를 표현하고 있는 데이터를 변경하면 되겠다.


제거하고 난 뒤 만약 진입차수가 0이 된 노드가 있다면 큐에 넣는다.



진입차수가 0인 노드들을 찾고, 딸린 간선을 제거하고,


다시 진입차수가 0인 노드들을 처리하는 부분문제로 이어진다고 생각하면 편하다.



사이클의 유무는 어떻게 판단할까?


만약 큐를 전부 소모했음에도 위상이 판단되지 않은 노드가 여전히 있다면 사이클때문임이 자명하다.



다음은 2252번 줄 세우기에 대한 해답이다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            q.push(i);
 
    while (!q.empty()) {
        int t = q.front();
        q.pop();
 
        printf("%d ", t);
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                q.push(next);
        }
    }
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

문명 


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



제대로 푼건지 모르겠다. 주변에 잘하시는 분들을 보면 다 유니온 파인드를 최적화하셨던데,


쌩 유니온 파인드로 제출했더니 맞긴했다.


나중에 재채점되면 틀릴 것 같지만, 일단 풀이를 공유하고자 한다.




맵에 k개의 문명 발상지가 있고, 매 턴마다 문명들은 사방향으로 진출하고, 경계선이 맞닿는다면(사방향) 해당 문명을 흡수한다.


이렇게 턴들이 진행될 때, 몇번째 턴에 모든 문명이 하나로 통일될 것인지 계산해야 한다.


예외적으로, 처음부터 k개의 발상지들이 모두 붙어있었다면, 바로 하나로 통일되고 답은 0이다.



사방향과 최소턴이라는 키워드로 일단 bfs를 쓰기로 했다.


탈출조건은, 문명이 줄고 줄어서 하나로 통일될 때 인데, 이를 구분하기 위해 유니온-파인드를 썼다.


맞닿는 경우에, 두 문명의 부모를 찾고, 다르다면 유니온하면서 문명 카운트를 하나 줄이는 것이다.


만약 카운트가 1이되면 bfs는 종료된다.



맞닿는 경우를 이중포문으로 어거지로 짠 것 같은데, 일단 맞았으니까 기분좋게 넘어간다.


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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <queue>
using namespace std;
 
int map[2000][2000];
int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
int n, k, a, b;
 
struct civil{
    int num;
    int y, x;
};
queue<civil> init, q;
 
int p[100001];
 
int find(int x){
    if (x == p[x])
        return x;
    else
        return p[x] = find(p[x]);
}
void unite(int x, int y){
    x = find(x);
    y = find(y);
 
    if (x != y)
        p[x] = y;
}
 
int main(){
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= k; ++i){
        scanf("%d %d", &a, &b);
        init.push({ i, b - 1, a - 1 });
        p[i] = i;
 
        map[b - 1][a - 1] = i;
    }
 
    while (!init.empty()){
        civil tmp = init.front();
        init.pop();
 
        for (int i = 0; i < 4; ++i){
            int yy = tmp.y + dir[i][0];
            int xx = tmp.x + dir[i][1];
 
            if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                continue;
 
            if (map[yy][xx] != 0){
                if (find(tmp.num) != find(map[yy][xx])){
                    unite(tmp.num, map[yy][xx]);
                    map[yy][xx] = tmp.num;
                    k--;
                }
            }
        }
        q.push({ map[tmp.y][tmp.x], tmp.y, tmp.x });
    }
 
    if (k == 1){
        printf("0");
        return 0;
    }
 
    int ans = 0;
    while (!q.empty()){
        ans++;
        int s = q.size();
        for (int i = 0; i < s; ++i){
            civil tmp = q.front();
            q.pop();
 
            for (int i = 0; i < 4; ++i){
                int yy = tmp.y + dir[i][0];
                int xx = tmp.x + dir[i][1];
 
                if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                    continue;
 
                if (map[yy][xx] != 0)
                    continue;
 
                map[yy][xx] = tmp.num;
                for (int j = 0; j < 4; ++j){
                    int yyy = yy + dir[j][0];
                    int xxx = xx + dir[j][1];
 
                    if (yyy < 0 || xxx < 0 || yyy >= n || xxx >= n)
                        continue;
 
                    if (map[yyy][xxx] != 0 && find(map[yyy][xxx]) != find(tmp.num)){
                        unite(tmp.num, map[yyy][xxx]);
                        k--;
 
                        if (k == 1){
                            printf("%d", ans);
                            return 0;
                        }
                    }
                }
                q.push({ tmp.num, yy, xx });
            }
        }
    }
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 12100 2048 (Easy)  (0) 2018.04.11
백준) 13460 구슬 탈출 2 // 구 째로탈출2  (0) 2018.04.11
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

오목


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



오목판이 주어지고 현재 누가 이겼는지를 판별해야한다.


모든 알을 보고 최대한 빨리 판별해보자.



오목에서 승리란 알을 연속으로 5개 두어야 생긴다. 방향은 가로, 세로, 대각선이 가능하다.


왼쪽 위부터 오른쪽으로, 아래로 모든 알을 본다면, 네 가지 방향으로 연속적인지만 판별하면 된다.


1. 아래 2. 오른쪽 3. 우하 대각선 4.우상 대각선



6개 두면 이긴게 아니기 때문에, 기존에 6개를 카운트 한 것을 방향 때문에 5개로 착각할 수 있다.


따라서 5개로 착각하지 않게 하기 위해, 정반대 방향의 돌을 하나 봐서, 현재 보는 돌이 시작점인지 확인할 수 있다.


visit으로 체크하는 방법은, 오목이 돌이 여러 방향들에 걸쳐진다는 점에서 쓸 수 없다.



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
#include <stdio.h>
 
int map[19][19];
int dir[4][2] = { {1,0},{1,1},{0,1},{-1,1} };
 
bool is_in_range(int y, int x) {
    return (y >= 0 && x >= 0 && y < 19 && x < 19);
}
 
int getMap(int y, int x) {
    if (y < 0 || x < 0 || y >= 19 || x >= 19)
        return 0;
    return map[y][x];
}
 
int main() {
    for (int i = 0; i < 19; ++i)
        for (int j = 0; j < 19; ++j)
            scanf("%d", &map[i][j]);
 
    int ans_y = -1, ans_x = -1, ans_c = -1;
 
    for (int d = 0; d < 4; ++d) {
        for (int x = 0; x < 19; ++x) {
            for (int y = 0; y < 19; ++y) {
                if (map[y][x] == 0)
                    continue;
 
                if (getMap(y - dir[d][0], x - dir[d][1]) == map[y][x])
                    continue;
 
                int yy = y, xx = x, cnt = 0;
                while (1) {
                    yy += dir[d][0];
                    xx += dir[d][1];
 
                    if (!is_in_range(yy, xx))
                        break;
 
                    if (map[yy][xx] != map[y][x])
                        break;
 
                    cnt++;
                }
                if (cnt == 4) {
                    ans_y = y;
                    ans_x = x;
                    ans_c = map[y][x];
                }
            }
        }
    }
 
    if (ans_c == -1) {
        printf("0");
        return 0;
    }
 
    printf("%d\n%d %d", ans_c, ans_y + 1, ans_x + 1);
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 13460 구슬 탈출 2 // 구 째로탈출2  (0) 2018.04.11
백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14

캥거루 세마리




캥거루 세 마리가 직선 위에 존재하고, 양 끝의 캥거루가 나머지 두 마리의 가운데로 점프해서 끼어들 수 있다.

단, 같은 지점에 두마리 이상 존재할 수 없을 때, 점프를 최대한 어람나 할 수 있을까?



세 마리가 동일한 지점에 있다면 항상 같은 결과가 나온다는 생각으로, dp를 시도해 볼 수 있다.


점프 이후 전에 계산했던 상황이 나오면 재활용 할 수 있는 것이다.


각 상황은 세 마리의 위치로 구분되므로, dp[100][100][100]으로 조질 수 있다. 최악의 경우 백만번의 연산을 수행한다.



재귀적으로 왼쪽, 오른쪽 캥거루가 움직일 경우에 최대 점프수를 알아내서, 그 중 최대값에 1을 더해주면 답이다.


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
int a, b, c;
int dp[100][100][100];
 
 
int func(int a, int b, int c) {
    if (a + 1 == b && b + 1 == c)
        return 0;
 
    int& ref = dp[a][b][c];
    if (ref != -1)
        return ref;
 
    int pp = 0;
    for (int p = a + 1; p < b; ++p) {
        int t = func(a, p, b);
        if (pp < t)
            pp = t;
    }
 
    int qq = 0;
    for (int q = b + 1; q < c; ++q) {
        int t = func(b, q, c);
        if (qq < t)
            qq = t;
    }
 
    return ref = max(pp, qq) + 1;
}
 
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d %d %d", &a, &b, &c);
    printf("%d", func(a, b, c));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준)15673 헤븐스 키친 2  (0) 2018.10.02
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

부분집합의 합 





각 원소들을 넣던지, 빼던지 해서 2가지 경우씩 발생한다. 따라서 모든 원소와 관련해 부분집합은 2^n개 생긴다.

원소가 최대 20개 이므로 브루트포스로 백만번의 연산으로 답을 얻을 수 있다.

하지만 분명 쓸따리 없는 연산도 존재한다.


가령 예를 들어 {0, 1, 2, 3, 4, 5}의 집합에서, S=6을 만드는 부분집합을 찾기위해, 첫 원소부터 넣을 것인지를 고려하다가,

{0, 1, 2, 3}까지 더해서 이미 6을 만들었는데, 나머지 {4, 5}를 넣을지 뺄지 고민할 필요가 없는 것이다.


하지만 이러한 가지치기(prunning)는 뒤의 수가 앞의 수보다 크다는 가정하에 진행되므로, 배열의 정렬이 필요하다.

정렬 이후엔 재귀안에 가지치는 코드를 넣어주자.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n[20], N, S, ans;
 
void dfs(int cur_sum, int cnt, int idx) {
    if (idx >= N)
        return;
 
    if (cur_sum + n[idx] > S) {
        if (n[idx] >= 0)
            return;
    }
 
    if (cur_sum + n[idx] == S)
        ans++;
 
    dfs(cur_sum + n[idx], cnt + 1, idx + 1);
    dfs(cur_sum, cnt, idx + 1);
}
 
int main() {
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; ++i)
        scanf("%d", &n[i]);
 
    sort(n, n + N);
    dfs(0, 0, 0);
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14

포도주 시식




포도주를 최대한 마시려고 한다. 앞에서 부터 잔들을 마실 수 있지만, 연속해서 세잔은 마실 수 없다.

계단 문제(http://js1jj2sk3.tistory.com/85?category=725178)와 같은 상황이다.

다만 한 번에 한 층만 오를 수 있게 조건만 변화했을 뿐이다.

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n;
int arr[10000];
int dp[10000][3];
 
int func(int p, int cnt) {
    if (p >= n)
        return 0;
 
    int& ref = dp[p][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(p + 1, 1) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else if (cnt == 1) {
        int a = func(p + 1, 2) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else
        return ref = func(p + 1, 0);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준)15673 헤븐스 키친 2  (0) 2018.10.02
백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

1로 만들기





디피로 완전탐색하자.


덜 논리적이라 디피는 재귀로 풀곤하는데(2)(완전 거의 대부분) 포문풀이(1)와 속도 차이가 4배정도 난다.


또한 재귀적으로 나누기 3의 상태를 보는게(3) 더 빠르다. 아마 더 빨리 1에 가까워져서가 아닐까 싶다



(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int dp[1000001];
 
int main() {
    int n, i;
    scanf("%d", &n);
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    for (i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
            dp[i] = dp[i / 2] + 1;
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
            dp[i] = dp[i / 3] + 1;
    }
    printf("%d", dp[n]);
}
cs


(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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    c = func(x - 1) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}
cs


(3)

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    c = func(x - 1) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01
백준) 2342 Dance Dance Revolution  (0) 2017.09.21

계단 오르기



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



계단을 오르면 점수를 얻는다. 도착지점 까지 일련의 규칙으로 올라갈 때, 얻을 수 있는 최고점은 얼마일까?



도착지점에서 생각해보면, 이 지점에 오기 위해서는 두 계단 밑이나, 한 계단 밑에서 올라왔을 것이다.


또한 그 지점 자체의 최고점이 존재할 것이며, 그 최고점은 두 계단 밑이나 한 계단 밑에서 올라오면서 형성된다.


따라서 각 층마다 상태를 dp로 저장해서 풀면 되겠다.



유의할 점은 한계단씩 연속으로 두번 오를 수 없다는 점이다.


즉 한번 한 계단만 올랐으면, 다음엔 반드시 두 계단을 올라야 한다.


그러면 한 층에서 상태는 두가지로 나눠지고 O(n * 2) 안에 풀 수 있다.



함수 func(int floor, int cnt) = floor층이고, 한 계단씩 연속해서 cnt번 올라왔을 때 얻는 최고점수를 계산해줌.


다음 층으로 오를 때는 cnt = 1이라면 2층 오르는 상태로 이어지며,


cnt = 0 이라면 한 계단 오르거나 두 계단 오르는 상태로 분기된다.



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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
 
#define M -987654321
 
 
int n;
int stair[301], dp[301][3];
 
 
int func(int floor, int cnt) {
    if (floor > n)
        return M;
 
    if (floor == n)
        return stair[n];
 
    int& ref = dp[floor][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(floor + 1, 1) + stair[floor];
        int b = func(floor + 2, 0) + stair[floor];
 
        return ref = max(a, b);
    }
    else if(cnt==1)
        return ref = func(floor + 2, 0) + stair[floor];
}
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &stair[i]);
        for (int j = 0; j < 3; ++j)
            dp[i][j] = -1;
    }
 
    printf("%d", max(func(1, 0), func(2, 0)));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01
백준) 2342 Dance Dance Revolution  (0) 2017.09.21
백준) 2618 경찰차  (1) 2017.09.17

피보나치 수 3




피보나치 수열은 다음과 같다.

0, 1, 1, 2, 3, 5, ...

n이 long long 범위 안으로 주어질 때 n번 째 피보나치 수를 구해라.



앞의 두 수를 더하면 피보나치 수가 생긴다. 하지만 n이 long long 범위이기 때문에 시간안에 구할 수 없다.

새로운 방법은 행렬을 사용하는 것이다.

f(n) = f(n-1) + f(n-2) // f(n-1) = f(n-1) 이므로,



여전히 행렬을 n-1번 곱해서 각 성분을 알야내야 한다는 점에서 시간복잡도는 줄지 않았다.

하지만 행렬이 곱셉에서 결합법칙이 성립한다는 점을 떠올린다면,

예를 들어 R^7 = R^4 * R^2 * R^1 로 분해할 수 있다는 것을 알 수 있다.


n-1은 long long 범위이므로 최대 2^64까지 커진다. 따라서 미리 2^0, 2^1, ... 2^63 까지 R의 제곱들을 구해놓으면,

log(n)시간에 답을 구할 수 있다. 위와 같이 4,2,1 제곱을 가져다 곱해주기만 하면 되기 때문이다.


소스는 다음과 같다.

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
#include <stdio.h>
#define mod 1000000
long long dp[64][2][2];
long long mat[2][2] = { {1ll,0ll},{0ll,1ll} };
long long n;
 
int main() {
    scanf("%lld", &n);
    if (n == 0) {
        printf("0");
        return 0;
    }
 
    if (n == 1) {
        printf("1");
        return 0;
    }
 
    dp[0][0][0] = 1ll, dp[0][0][1] = 1ll;
    dp[0][1][0] = 1ll, dp[0][1][1] = 0ll;
 
    for (int i = 1; i < 64; ++i) {
        dp[i][0][0] =
            ((dp[i - 1][0][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][0][1] =
            ((dp[i - 1][0][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][0][1] * dp[i - 1][1][1]) % mod) % mod;
        dp[i][1][0] =
            ((dp[i - 1][1][0] * dp[i - 1][0][0]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][0]) % mod) % mod;
        dp[i][1][1] =
            ((dp[i - 1][1][0] * dp[i - 1][0][1]) % mod +
            (dp[i - 1][1][1] * dp[i - 1][1][1]) % mod) % mod;
    } // 행렬의 2^i 제곱을 미리 구해놓는다.
 
 
    n--;
    for (int i = 0; (1ll << i) <= n; ++i) {
        if ((n & (1ll << i)) != 0) {
            long long tmp[2][2];
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    tmp[a][b] = mat[a][b];
 
            mat[0][0] =
                ((tmp[0][0] * dp[i][0][0]) % mod +
                (tmp[0][1] * dp[i][1][0]) % mod) % mod;
            mat[0][1] =
                ((tmp[0][0] * dp[i][0][1]) % mod +
                (tmp[0][1] * dp[i][1][1]) % mod) % mod;
            mat[1][0] =
                ((tmp[1][0] * dp[i][0][0]) % mod +
                (tmp[1][1] * dp[i][1][0]) % mod) % mod;
            mat[1][1] =
                ((tmp[1][0] * dp[i][0][1]) % mod +
                (tmp[1][1] * dp[i][1][1]) % mod) % mod;
        }
    }
 
    printf("%lld\n", mat[0][0]);
 
    return 0;
}
cs


'알고리즘 > 수학' 카테고리의 다른 글

백준) 4948 베르트랑 공준 (에라토스테네스의 체)  (0) 2018.01.31
백준) 2609 최대공약수와 최소공배수  (0) 2017.09.13
백준) 10973 이전 순열  (0) 2017.09.11
백준) 10972 다음 순열  (0) 2017.09.11
백준) 9742 순열  (0) 2017.09.03

RGB거리




각 집들을 칠하는데 비용을 최소화해야 한다.

칠하는 색은 세 종류가 있고, 각 집마다 세가지 색을 칠하는 비용이 다르게 주어진다.

또한 이웃집의 색이 같을 수 없다. 0번 집을 빨갛게 칠했으면, 1번 집은 다르게 칠해야 한다.


모든 경우를 탐색한다면 3 ^ n 만큼 걸린다.

하지만 규칙에 따르면 같은 색을 연속해서 쓸 수 없고, 비용은 최소화해야 하기 때문에

다이나믹 프로그래밍으로 조질 수 있겠다.

n개째 집을 칠하는 비용은 n-1개의 집을 칠하는 최소비용에 더해지기 때문이다.


각 상태는 몇 번째 집을 칠하고 있는지, 색은 무엇인지로 구분된다.

배열은 dp[집의 수][색의 종류]로 잡자.


집을 앞에서 부터 연속적으로 칠한다면, 함수는 다음과 같다.

func(int num, int color) = num번째 집을 color로 칠하는 최소비용을 계산해줌.

그러면 정답은 func(n-1, 0), func(n-1, 1), func(n-1, 2) 중에 작은 값이다.


함수는 다음과 같이 퍼진다.

색을 0으로 칠했다면 최소비용은 func(n-1, 1)과 func(n-1, 2)중에 있다.

계속 퍼져나가다가 n==0이 되면 더 이상 퍼지지 않는다.


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
#include <stdio.h>
#include <string.h>
#include <algorithm>
 
#define init -987654321
 
int n;
int dp[1000][3];
int cost[1000][3];
 
 
int func(int num, int color) {
    if (num == 0)
        return cost[0][color];
 
    int& ref = dp[num][color];
    if (ref != init)
        return ref;
 
    int min = -init;
    for (int i = 0; i < 3; ++i) {
        if (i == color)
            continue;
 
        int t = func(num - 1, i);
        if (min > t)
            min = t;
    }
 
    return ref = min + cost[num][color];
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            scanf("%d", &cost[i][j]);
            dp[i][j] = init;
        }
    }
 
    int ans = -init;
    for (int i = 0; i < 3; ++i) {
        if (ans > func(n - 1, i))
            ans = dp[n - 1][i];
    }
    printf("%d", ans);
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 2342 Dance Dance Revolution  (0) 2017.09.21
백준) 2618 경찰차  (1) 2017.09.17
백준) 2098 외판원 순회  (1) 2017.09.17

+ Recent posts

티스토리툴바