반응형

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

 

17135번: 캐슬 디펜스

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dfs를 이용하여 궁수의 위치를 정하고, 시뮬레이션을 통해서 죽인 적의 최댓값을 ans에 저장해 출력하였습니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M, D;
int arr[15][15];
int arrow[3];
int ans;
 
int cnt()        //죽인 적의 수
{
    int temp[16][15] = { 0 };
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            temp[i][j] = arr[i][j];
        }
    }
 
    int ret = 0;
 
    while (1) {
        vector<pair<int, int>> die;    //죽일 수 있는 적의 좌표 저장
        for (int k = 0; k < 3; k++) {
            int min = 987654321;
            int y;
            int x;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (temp[j][i] == 1) {
                        if (min > abs(arrow[k] - i) + N - j) {
                            y = j;
                            x = i;
                            min = abs(arrow[k] - i) + N - j;
                        }
                    }
                }
            }
            if (min <= D) {    //거리 안에 있다면 좌표 저장
                die.push_back({ y,x });
            }
        }
        for (auto next : die) {    //좌표가 중복될 수 있으므로 한번에 처리
            if (temp[next.first][next.second] == 1) {
                temp[next.first][next.second] = 0;
                ret++;
            }
        }
        for (int i = N - 1; i >= 0; i--) {    //한칸씩 밀기
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 1) {
                    temp[i + 1][j] = 1;
                    temp[i][j] = 0;
                }
            }
        }
 
        int flag = 0;
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (temp[i][j] == 1) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) break;
        }
        if (flag == 0) break;    //적이 하나도 없다면
    }
    return ret;
}
 
void dfs(int level, int num)
{
    if (level == 3) {
        ans = max(cnt(), ans);
        return;
    }
 
    for (int i = num; i < M; i++) {    //궁수의 위치
        arrow[level] = i;
        dfs(level + 1, i + 1);
        arrow[level] = -1;
    }
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &D);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    dfs(0, 0);
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1003번 - 피보나치 함수 (C++)  (0) 2022.09.03
[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
반응형

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

 

16637번: 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순

www.acmicpc.net

 

 

[ 문제풀이 ]

 

dfs를 이용하여 괄호의 위치를 정하고, 그 괄호를 바탕으로 수식을 계산하여 최댓값을 ans에 저장하는 방식으로 풀었습니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
char arr[20];    //식
int visited[20];    //괄호 여부
int ans = -987654321;
 
void dfs(int level, int limit, int num)
{
    if (level == limit) {
        int ret = arr[0] - '0';
        int before;
        for (int i = 1; i < N; i += 2) {
            if (visited[i] == -1) {    //괄호 안에 있는 연산자라면
                int temp;
                if (arr[i] == '+') {
                    temp = (arr[i - 1] - '0') + (arr[i + 1] - '0');
                }
                else if (arr[i] == '-') {
                    temp = (arr[i - 1] - '0') - (arr[i + 1] - '0');
                }
                else if (arr[i] == '*') {
                    temp = (arr[i - 1] - '0') * (arr[i + 1] - '0');
                }
 
                if (i != 1) {
                    if (arr[i-2] == '+') {
                        ret = ret - (arr[i-1]-'0') + temp;
                    }
                    else if (arr[i-2] == '-') {
                        ret = ret + (arr[i-1]-'0') - temp;
                    }
                    else if (arr[i-2] == '*') {
                        if (arr[i - 1] - '0' == 0) {
                            ret = before * temp;
                        }
                        else {
                            ret = ret / (arr[i - 1] - '0') * temp;
                        }
                    }
                }
                else {
                    ret = temp;
                }
            }
            else {    //괄호 밖의 연산자라면
                if (arr[i] == '+') {
                    ret += arr[i + 1] - '0';
                }
                else if (arr[i] == '-') {
                    ret -= arr[i + 1] - '0';
                }
                else if (arr[i] == '*') {
                    if (arr[i + 1] - '0' == 0) {
                        before = ret;
                        ret = 0;
                    }
                    else {
                        ret *= arr[i + 1] - '0';
                    }
                }
            }
        }
        ans = max(ans, ret);
        return;
    }
 
    for (int i = num; i < N; i++) {
        if (i % 2 == 1) {
            if (visited[i] == 0) {
                visited[i] = -1;
                visited[i + 2] = 1;
                dfs(level + 1, limit, i + 4);
                visited[i] = 0;
                visited[i + 2] = 0;
            }
        }
    }
}
 
int main()
{
    scanf("%d", &N);
 
    scanf("%s", arr);
 
    for (int i = 0; i <= (N + 1) / 4; i++) {    //괄호의 개수
        dfs(0, i, 1);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16234번 - 인구 이동 (C++)  (0) 2022.09.02
[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
반응형

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

매우 기본적인 bfs문제입니다. 방향 배열을 통해서 인접한 4방향으로 이동하고, visited배열을 통해서 방문을 체크해주면 됩니다. 지도에서 값이 1인 길일 때만 queue에 push 해주고, 방문을 한 번이라도 했다면 그 좌표는 무시해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
struct node {
    int y;
    int x;
    int cnt;
};
 
int N, M;
char arr[100][101];
int visited[100][100];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        scanf("%s", arr[i]);
    }
 
    queue<node> q;
    q.push({ 0,0,1 });
 
    while (!q.empty())
    {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        if (y == N - 1 && x == M - 1) {
            printf("%d", cnt);
            return 0;
        }
 
        if (visited[y][x]) continue;
        visited[y][x] = 1;
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy >= 0 && yy < N && xx >= 0 && xx < M) {
                if (arr[yy][xx] == '1' && visited[yy][xx] != 1) {
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17135번 - 캐슬 디펜스 (C++)  (0) 2022.09.01
[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
반응형

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

 

11400번: 단절선

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/115?category=1064608 

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
struct Edge {
    int start;
    int end;
};
 
bool cmp(Edge left, Edge right)
{
    if (left.start == right.start) return left.end < right.end;
    return left.start < right.start;
}
 
int V, E;
vector<int> list[100001];
int id[100001];
vector<Edge> ans;
int cur = 1;
 
int dfs(int node, int parent)
{
    id[node] = cur++;
    int ret = id[node];
 
    for (auto next : list[node]) {
        if (next == parent) continue;    //부모를 제외하고
        if (id[next]) {
            ret = min(ret, id[next]);
            continue;
        }
 
        int minId = dfs(next, node);    //갈 수 있는 가장 낮은 id
 
        if (minId > id[node]) {    //간선을 오름차순으로 정렬
            ans.push_back({ min(node,next), max(node,next) });
        }
 
        ret = min(ret, minId);
    }
    return ret;
}
 
int main()
{
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    for (int i = 1; i <= V; i++) {
        if (!id[i]) {
            dfs(i, 0);
        }
    }
 
    sort(ans.begin(), ans.end(), cmp);    //시작 간선을 기준으로 오름차순 정렬
 
    printf("%d\n", ans.size());
 
    for (auto edge : ans) {
        printf("%d %d\n", edge.start, edge.end);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16637번 - 괄호 추가하기 (C++)  (0) 2022.08.31
[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
반응형

1. 단절선(Articulation Bridge)이란?

 

단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말합니다.

 

2. 단절선(Articulation Bridge)동작 원리?

 

단절선(Articulation Bridge)의 동작 원리는 단절점(Articulation Point)의 동작 원리와 비슷합니다.

https://rudalsd.tistory.com/113

 

[ 알고리즘 ] 단절점(Articulation Point)

1. 단절점(Articulation Point)이란? 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정

rudalsd.tistory.com

 

단절점(Articulation Point)과의 차이점은 루트노드가 사라진 것과 부모 노드를 제외한 나머지 노드들이 우회 간선을 이용해서도 현재 노드에 도착하면 안되므로 등호가 빠진 것입니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 이분 매칭(Bipartite Matching)  (0) 2023.05.24
[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)  (0) 2022.10.24
[ 알고리즘 ] 단절점(Articulation Point)  (0) 2022.08.26
[ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component)  (0) 2022.07.23
[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)  (0) 2022.07.19
반응형

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

 

11266번: 단절점

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/113?category=1064608

 

[ 알고리즘 ] 단절점(Articulation Point)

1. 단절점(Articulation Point)이란? 단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정

rudalsd.tistory.com

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int V, E;
vector<int> list[10001];
int id[10001];
int ans[10001];
int cur = 1;
 
int dfs(int node, bool root)
{
    id[node] = cur++;
    int ret = id[node];
    int child = 0;
 
    for (auto next : list[node]) {
        if (id[next]) {    //이미 방문했다면
            ret = min(ret, id[next]);
            continue;
        }
        child++;    //자식의 개수
 
        int minId = dfs(next, false);    //갈수 있는 노드 중 가장 id값이 낮은 노드
 
        if (!root && minId >= id[node]) {    //루트가 아니고 자신보다 더 낮은 id값을 가진 노드로 가지 못할 때
            ans[node] = 1;
        }
 
        ret = min(ret, minId);
    }
 
    if (root && child > 1) {
        ans[node] = 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++) {        //그래프 만들기
        int a, b;
        scanf("%d %d", &a, &b);
        list[a].push_back(b);
        list[b].push_back(a);
    }
 
    for (int i = 1; i <= V; i++) {    //방문하지 않은 노드라면
        if (!id[i]) {
            dfs(i, true);
        }
    }
 
    int cnt = 0;
 
    for (int i = 1; i <= V; i++) {    //단절점의 개수
        if (ans[i] == 1) cnt++;
    }
 
    printf("%d\n", cnt);
 
    for (int i = 1; i <= V; i++) {    //단절점 출력
        if (ans[i] == 1) printf("%d ", i);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2178번 - 미로 탐색 (C++)  (0) 2022.08.30
[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
반응형

1. 단절점(Articulation Point)이란?

 

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말합니다.

 

2. 단절점(Articulation Point)동작 원리?

 

dfs를 활용하여 O(V+E)의 시간복잡도로 문제를 해결할 수 있습니다.

 

위 그래프의 방문 순서에 따라 id값을 매깁니다. id값은 1부터 시작하여 1씩 증가합니다. 방문 순서는 1→3→4→5→2→6이 됩니다.

 

방문하지 않은 노드를 방문할 때마다 dfs를 수행하여 단절점을 확인해보겠습니다.

 

단절점의 발견 조건은 특정 i번 노드에서 자식 노드들이 노드 i를 거치지 않고 노드 i보다 낮은 id값을 가진 노드로 갈 수 없다면 단절점입니다. 또한 현재 노드가 루트 노드일 때 자식 노드가 2개 이상이라면 단절점입니다.

 

 

4번과 5번 노드는 3번 노드를 거치지 않으면 1번 노드로 가지 못합니다. 따라서 3번 노드는 단절점입니다.

 

위와 같은 방법으로 2번 노드와 6번 노드는 5번 노드를 거쳐야하고, 6번 노드는 2번 노드를 거쳐야하므로 2번 노드와 5번 노드 또한 단절점입니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'알고리즘' 카테고리의 다른 글

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)  (0) 2022.10.24
[ 알고리즘 ] 단절선(Articulation Bridge)  (0) 2022.08.28
[ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component)  (0) 2022.07.23
[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)  (0) 2022.07.19
[ 알고리즘 ] KMP 알고리즘(KMP Algorithm)  (0) 2022.07.19
반응형

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

 

3653번: 영화 수집

각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/51?category=1073064 

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. pos배열을 이용하여 1 ~ n까지의 DVD가 몇 번 idx에 있는지 저장합니다.

 

2. n + m개의 리프가 있는 세그먼트 트리를 만들어서 1 ~ n개까지의 리프를 채웁니다.

 

3. 원하는 DVD의 idx를 0으로 업데이트합니다.

 

4. idx부터 n+i까지 dvd의 개수를 구한 후 출력합니다.

 

5. n+i 리프를 1로 업데이트합니다.

 

6. 원하는 DVD의 idx를 n+i로 갱신해줍니다.

 

7. 위의 과정을 반복합니다.

 

[ 소스 코드 ]

 

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
#include<iostream>
#include<vector>
#include<cmath>
 
using namespace std;
 
int n, m;
vector<int> segmentTree;
int pos[100001];
 
int makeTree(int node, int start, int end)        //트리 만들기
{
    if (start == end) {
        if (start <= n) {
            return segmentTree[node] = 1;
        }
        else {
            return 0;
        }
    }
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segmentTree[node] = left + right;
}
 
void get(int node, int start, int end, int idx)    //dvd 빼기
{
    if (idx < start || idx > end) {
        return;
    }
    else {
        segmentTree[node]--;
    }
 
    if (start == end) return;
 
    int mid = (start + end) / 2;
    get(node * 2, start, mid, idx);
    get(node * 2 + 1, mid + 1, end, idx);
}
 
void put(int node, int start, int end, int idx)    //dvd 넣기
{
    if (idx < start || idx > end) {
        return;
    }
    else {
        segmentTree[node]++;
    }
 
    if (start == end) return;
 
    int mid = (start + end) / 2;
    put(node * 2, start, mid, idx);
    put(node * 2 + 1, mid + 1, end, idx);
}
 
int sum(int node, int start, int end, int sidx, int eidx)    //합 구하기
{
    if (sidx > end || eidx < start) return 0;
    if (sidx <= start && end <= eidx) return segmentTree[node];
 
    int mid = (start + end) / 2;
    int left = sum(node * 2, start, mid, sidx, eidx);
    int right = sum(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            pos[i] = n - i + 1;
        }
        int size = (1 << (int)ceil(log2(n+m)) + 1);
        segmentTree.clear();
        segmentTree.resize(size);
        makeTree(1,1,n+m);
 
        for (int i = 1; i <= m; i++) {
            int num;
            scanf("%d", &num);
            get(1, 1, n + m, pos[num]);
            printf("%d ", sum(1, 1, n + m, pos[num], n + i - 1));
            put(1, 1, n + m, n + i);
            pos[num] = n + i;
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11400번 - 단절선 (C++)  (0) 2022.08.29
[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
반응형

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

 

1533번: 길의 개수

첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000

www.acmicpc.net

 

 

[ 문제풀이 ]

 

가중치가 있는 행렬의 이동 가능한 경로의 개수를 구하기 위해서는 가중치가 없는(가중치가 1인) 행렬로 바꿔주어야 합니다.

 

가중치의 최댓값이 5이기 때문에 노드 하나를 5개로 나누어 가중치가 없는 행렬로 만듭니다.

 

예를 들어 u→v로 가는 데 걸리는 시간이 3이라면 u→v2→v1→v0을 통해 이동하면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
 
#define M 1000003
#define ll long long
 
using namespace std;
 
int N, S, E, T;
unordered_map<int, vector<vector<ll>>> m;
vector<vector<ll>> vect(50, vector<ll>(50, 0));
 
vector<vector<ll>> multi(vector<vector<ll>> a, vector<vector<ll>> b)    //행렬 곱셈
{
    vector<vector<ll>> ret(N * 5, vector<ll>(N * 5, 0));
    for (int i = 0; i < N * 5; i++) {
        for (int j = 0; j < N * 5; j++) {
            int sum = 0;
            for (int k = 0; k < N * 5; k++) {
                sum += ((a[i][k] % M) * (b[k][j] % M))%M;
                sum %= M;
            }
            ret[i][j] = sum;
        }
    }
 
    return ret;
}
 
vector<vector<ll>> conquer(int num)        //분할 정복
{
    if (m.count(num) != 0) return m[num];
    if (num == 1) return vect;
    if (num % 2 == 1) {
        return m[num] = multi(conquer(num - 1), conquer(1));
    }
    else {
        return m[num] = multi(conquer(num / 2), conquer(num / 2));
    }
}
 
int main()
{
    scanf("%d %d %d %d", &N, &S, &E, &T);
 
    vector<vector<ll>> ans;
 
    for (int i = 0; i < N; i++) {        //입력 받은 가중치가 있는 행렬을 가중치가 없는 
        string str;                        //행렬로 바꾸기
        cin >> str;
        for (int j = 0; j < N; j++) {
            int num = str[j] - '0';
            if (num > 0) {
                vect[i * 5][j * 5 + num - 1] = 1;
            }
            for (int k = 0; k < 4; k++) {
                vect[j * 5 + k + 1][j * 5 + k] = 1;
            }
        }
    }
 
    ans = conquer(T);
 
    printf("%d", ans[(S - 1) * 5][(E - 1) * 5]);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 11266번 - 단절점 (C++)  (0) 2022.08.27
[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 11286번 - 절댓값 힙 (C++)  (0) 2022.08.23
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
반응형

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

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. struct를 만들어 입력된 수와 절댓값을 저장합니다.

 

2. pq에 절댓값이 낮은 순으로 정렬하고, 같다면 수가 낮은 순으로 정렬합니다.

 

3. 0이 입력되면 pq에서 하나씩 뽑아가면서 출력합니다.

 

[ 소스 코드 ]

 

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
#include<cstdio>
#include<queue>
#include<cmath>
 
using namespace std;
 
struct node {
    int num;
    int absolute;
};
 
struct cmp {
    bool operator()(node right, node left) {
        if (right.absolute == left.absolute) return left.num < right.num;
        return left.absolute < right.absolute;
    }
};
 
int main()
{
    priority_queue<node, vector<node>, cmp> pq;
    int N;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        if (x != 0) {
            pq.push({ x,abs(x) });
        }
        else {
            if (!pq.empty()) {
                printf("%d\n", pq.top().num);
                pq.pop();
            }
            else {
                printf("%d\n", 0);
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 3653번 - 영화 수집 (C++)  (0) 2022.08.25
[ 백준 ] 1153번 - 길의 개수 (C++)  (0) 2022.08.24
[ 백준 ] 3176번 - 도로 네트워크 (C++)  (0) 2022.08.22
[ 백준 ] 1780번 - 종이의 개수 (C++)  (0) 2022.08.21
[ 백준 ] 1931번 - 회의실 배정 (C++)  (0) 2022.08.20

+ Recent posts

티스토리툴바