문제 : https://www.acmicpc.net/problem/18808

시뮬레이션

[ 문제해석 ]

 map에 입력된 스티커를 붙이는데 이미 스티커가 없는 부분에만 스티커를 붙일 수 있고, 스티커가 범위 밖으로 나가도 안된다. 스티커를 붙일 수 있는 지점이 여러 곳이 있다면 위쪽, 왼쪽에 우선순위를 주어 스티커를 붙이고, 현재 스티커를 붙일 지점이 없다면 스티커를 90도 씩 회전시켜서 확인해본다. 90도 씩 4번 회전해서 원래 모양으로 돌아왔는데도 붙일 지점이 없었다면 스티커를 버린다.

 

[ 알고리즘풀이 ]

 일단 Input 크기가 굉장히 작다 --> 단순 시뮬레이션으로 모든 경우를 커버해도 된다.

 

 1) 위쪽 / 왼쪽에 우선순위를 주어 스티커를 붙여야 하므로, 스티커를 map의 좌측 상단부터 시작해서 차례대로 모든 지점에서 스티커를 붙여본다.

 2) 스티커를 붙일 수 있다면, 붙이고 map에 체크해주고 넘어간다.

 3) 스티커를 붙일 수 없다면, rotate를 시켜서 다시 1) 과정을 거친다. 이때, 주의할 부분은 rotate를 시키면 기존의 스티커 행과 열이 바뀌게 된다! 예를 들어, 5x2 크기의 스티커는 2x5 크기로 바뀐다. 

 4) rotate를 4번 진행했는데도 붙일 수 없다면 다음 스티커로 넘어간다.

 

[ 코드 C++ ]

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
#include<iostream>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int mapRows, mapCols, stickers;
    bool map[40][40] = {};
    cin >> mapRows >> mapCols >> stickers;
    for (int sticker = 0; sticker < stickers; sticker++) {
        // 스티커 입력
        int stickerRows, stickerCols;
        bool stickerMap[10][10] = {};
        cin >> stickerRows >> stickerCols;
        for (int stickerR = 0; stickerR < stickerRows; stickerR++)
            for (int stickerC = 0; stickerC < stickerCols; stickerC++)
                cin >> stickerMap[stickerR][stickerC];
 
        // 4방향에 대해서 스티커를 위, 왼쪽부터 붙여보자.
        for (int rotate = 0; rotate < 4; rotate++) {
            bool success = false;
            for (int j = 0; j <= mapRows - stickerRows; j++) {
                for (int k = 0; k <= mapCols - stickerCols; k++) {
                    // map의 (j,k) 에서 시작해서 스티커를 붙여보자.
                    bool fail = false;
                    for (int stickerR = 0; stickerR < stickerRows; stickerR++) {
                        for (int stickerC = 0; stickerC < stickerCols; stickerC++) {
                            // 이미 스티커가 붙은 곳에 붙여야하는 경우
                            if (map[j + stickerR][k + stickerC] && stickerMap[stickerR][stickerC]) { 
                                fail = true;
                                stickerR = stickerRows, stickerC = stickerCols;
                            }
                        }
                    }
                    if (!fail) {
                        for (int stickerR = 0; stickerR < stickerRows; stickerR++)
                            for (int stickerC = 0; stickerC < stickerCols; stickerC++)
                                if (stickerMap[stickerR][stickerC]) map[j + stickerR][k + stickerC] = 1;
                        j = mapRows - stickerRows + 1, k = mapCols - stickerCols + 1; //break;
                        success = true;
                    }
                }
            }
            if (success) break;
 
            // 90도 회전시키자
            bool copyStickerMap[10][10] = {};
            for(int stickerR = 0; stickerR < stickerCols; stickerR++)
                for(int stickerC = 0; stickerC < stickerRows; stickerC++)
                    copyStickerMap[stickerR][stickerC] = stickerMap[stickerRows- 1 - stickerC][stickerR];
            int temp = stickerRows; // 회전하니까 row, col SWAP
            stickerRows = stickerCols;
            stickerCols = temp;
            for (int stickerR = 0; stickerR < 10; stickerR++) // 회전시킨 copyMap 복사해주기
                for (int stickerC = 0; stickerC < 10; stickerC++)
                    stickerMap[stickerR][stickerC] = copyStickerMap[stickerR][stickerC];
 
        }
    }
    int ans = 0;
    for (int mapR = 0; mapR < mapRows; mapR++)
        for (int mapC = 0; mapC < mapCols; mapC++)
            if (map[mapR][mapC]) ans++;
 
    cout << ans << '\n';
}
 cs

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ18808.cpp

 

travelbeeee/BOJ

백준 문제풀이. Contribute to travelbeeee/BOJ development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21
[BOJ] 2517 : 달리기  (0) 2020.08.14
[BOJ] 10167 : 금광  (0) 2020.08.13

문제 : https://www.acmicpc.net/problem/10282

다익스트라 최단거리 그래프

[ 문제해석 ]

 

 component 들이 서로 의존하는 상황이고, 하나의 component 에서 fail 이 시작하면 다른 의존하는 component 들도 영향을 받는다. 이때, 하나의 component 에서 fail이 시작되면 몇 개의 component 가 fail이 되고, 모든 component 들이 fail 될 때까지 얼마나 시간이 걸리는지 계산하라.

 

[ 알고리즘풀이 ]

 

 fail이  처음 일어나는 component 에서 Dijkstra 알고리즘으로 다른 모든 영향을 줄 수 있는 component 까지의 최단 거리를 구하면 몇 개의 component 가 fail이 되는지 알 수 있다. 또, 모든 component 들이 fail이 될 때까지 걸리는 시간은 최단거리 중 가장 긴 거리이므로 Dijkstra 알고리즘으로 문제를 해결할 수 있다.

 

[ 코드 C++ ]

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
/*
    시작점 C에서 시작해서 다른 system으로 이동하며 감염을 시키는 문제
    --> c에서 시작해서 다른 system까지 최단거리를 dijkstra를 이용해 구하자.
    --> 경로가 있다면 cnt, 경로 중 가장 긴 거리가 최대 시간!
*/
 
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t;
    const int INF = 99999999;
    cin >> t;
    while (t--) {
        int n, d, c;
        vector<pair<int, int>> map[10001];
 
        cin >> n >> d >> c;
        for (int i = 0, a, b, c; i < d; i++) {
            cin >> a >> b >> c;
            map[b].push_back({ a, c });
        }
 
        vector<int> distance(n + 1, INF);
        distance[c] = 0;
        priority_queue<pair<int, int>> pq;
        pq.push({ 0, c });
        while (!pq.empty()) {
            int cost = -pq.top().first;
            int here = pq.top().second;
            pq.pop();
 
            if (distance[here] < cost) continue;
            for (int i = 0; i < map[here].size(); i++) {
                int next = map[here][i].first;
                int nextD = cost + map[here][i].second;
                if (nextD < distance[next]) {
                    distance[next] = nextD;
                    pq.push({ -nextD, next });
                }
            }
        }
 
        int cnt = 0, maxL = -INF;
        for(int i = 1; i <= n; i++)
            if (distance[i] != INF) {
                cnt++;
                maxL = max(maxL, distance[i]);
            }
 
        cout << cnt << ' ' << maxL << '\n';
    }
}
 cs

[ github ]

https://github.com/travelbeeee/BOJ/blob/master/BOJ10282.cpp

 

travelbeeee/BOJ

백준 문제풀이. Contribute to travelbeeee/BOJ development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 2517 : 달리기  (0) 2020.08.14
[BOJ] 10167 : 금광  (0) 2020.08.13
[BOJ] 1194 : 달이 차오른다, 가자.  (0) 2020.08.07

문제 : https://www.acmicpc.net/problem/2517

세그먼트트리

[ 문제해석 ]

 

 현재 달리고 있는 선수들의 순서대로 선수들의 능력치가 입력으로 들어옵니다. 이때, 자기 능력치보다 적은 선수가 앞에서 달리고 있으면 '앞지를 수 있는 가능성' 이 존재합니다. 선수들의 능력치가 입력으로 들어왔을 때 각 선수가 얻을 수 있는 최선의 등수를 찾는 문제입니다.

 

[ 알고리즘풀이 ]

 

1) '선수가 얻을 수 있는 최선의 등수' = '지금 등수' - '앞지를 수 있는 선수의 수' 를 이용하면 됩니다. 즉 내가 3등인데 앞에 2명을 앞지를 수 있으면 최선의 등수는 1등이 됩니다.

 이때, '앞지를 수 있는 선수' 는 나보다 앞에 있으면서 능력치가 나보다 작은 선수가 됩니다.

 --> "나보다 앞의 범위에서 능력치가 나보다 작은 선수를 count 하자!" 로 문제를 단순화 할 수 있습니다. 

 --> 세그먼트 트리를 이용해 앞의 범위에서 능력치가 나보다 작은 선수를 count 하자!

 

2) N은 500,000 지만 입력되는 범위는 1 ~ 10^9이므로 좌표압축을 통해서 능력치 대신에 능력치를 낮은 순으로 등수를 매긴 값으로 갱신해줍니다.

 예제를 보면 [ 2, 8, 10, 7, 1, 9, 4, 15 ] 능력치를 입력받습니다.

 이를 능력치 낮은 순으로 [ 2, 5, 7, 4, 1, 6, 3, 8 ] 로 등수를 매겨 새롭게 값을 갱신해줍니다. 

 

3) 등수를 이용해 세그먼트 트리를 만듭니다.

 0으로 초기화된 세그먼트 트리에서 앞의 선수부터 등수에 해당하는 인덱스를 '1'로 세그먼트 트리를 갱신합니다.  따라서, 자신보다 앞에 있는 범위를 전체 sum 한다면 자신보다 앞에 있는 능력치가 작은 선수들을 한 번에 count 할 수 있게 됩니다.

 

예제를 통해 생각해보겠습니다. 

 

능력치  [ 2, 8, 10, 7, 1, 9, 4, 15]

등수 [ 2, 5, 7, 4, 1, 6, 3, 8 ]

초기세그먼트 [ 0 0 0 0 0 0 0 0 ]

--> '능력치 낮은 순 2등' 세그먼트트리 [ 0 1 0 0 0 0 0 0 ]

--> (1~1 범위를 sum) = 0 이므로 0명을 앞지를 수 있다. --> (현재1등) - (0명) = 최대 1등

--> '능력치 낮은 순 5등' 세그먼트트리 [ 0 1 0 0 1 0 0 0 ]

--> (1~4 범위를 sum) = 1 이므로 1명을 앞지를 수 있다. --> (현재2등) - (1명) = 최대 1등

--> '능력치 낮은 순 7등' 세그먼트트리 [ 0 1 0 0 1 0 1 0 ]

--> (1~6 범위를 sum) = 2 이므로 2명을 앞지를 수 있다. --> (현재3등) - (2명) = 최대 1등

 

 위와 같은 과정을 반복하면 된다.

 

[ 코드 C++ ]

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
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
 
using namespace std;
 
const int N_MAX = 500000;
int ab[N_MAX];
vector<int> sortedAb;
ll tree[4 * N_MAX];
 
ll sum(int index, int start, int end, int left, int right) {
    if (end < left || right < start)
        return 0;
    if (left <= start && end <= right)
        return tree[index];
    int mid = (start + end) / 2;
    return sum(2 * index + 1, start, mid, left, right) + sum(2 * index + 2, mid + 1, end, left, right);
}
 
ll update(int index, int start, int end, int changed, int diff) {
    if (changed < start || end < changed) return tree[index];
    if (start == end) return tree[index] = diff;
    int mid = (start + end) / 2;
    return tree[index] = update(index * 2 + 1, start, mid, changed, diff) + update(index * 2 + 2, mid + 1, end, changed, diff);
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> ab[i];
        sortedAb.push_back(ab[i]);
    }
    sort(sortedAb.begin(), sortedAb.end());
 
    for (int i = 0; i < N; i++) {
        int ind = (lower_bound(sortedAb.begin(), sortedAb.end(), ab[i]) - sortedAb.begin());
        update(0, 0, N - 1, ind, 1);
        cout << (i + 1) - sum(0, 0, N - 1, 0, ind - 1) << '\n';
    }
    return 0;
}
 cs

https://github.com/travelbeeee/BOJ/blob/master/BOJ2517.cpp

 

travelbeeee/BOJ

백준 문제풀이. Contribute to travelbeeee/BOJ development by creating an account on GitHub.

github.com

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21
[BOJ] 10167 : 금광  (0) 2020.08.13
[BOJ] 1194 : 달이 차오른다, 가자.  (0) 2020.08.07
[BOJ] 17025 : Icy Perimeter  (0) 2020.07.30

문제 : https://www.acmicpc.net/problem/10167

세그먼트트리 분할정복 좌표압축

[ 문제해석 ]

 2차원 평면에 N개의 금광이 존재하고, 금광마다 벌 수 있는 수익이 다 다르다. x축과 y축에 평행한 직사각형을 그려서 직사각형 안에 있는 금광으로 얻을 수 있는 최대 수익을 구해보자.

 

[ 알고리즘풀이 ]

 N이 3000으로 우리는 O(N^2 * logN) 이나 O(N^2) 로 문제를 해결해야한다.

 문제를 단순화해보자.

 

1)  직사각형을 그릴 때 금광이 없는 x값, y값에다가 굳이 직사각형을 그릴 필요가 없다.

 위의 그림과 같이 금광 4개를 포함하는 직사각형은 여러가지 경우가 있지만 우리는 '직사각형2'처럼 금광들의 x값, y값을 기준으로 포함하는 가장 작은 직사각형만 그려봐도 된다!

--> 금광을 기준으로 직사각형을 그리자.

--> 금광 2개를 정하면 그 금광을 기준으로 직사각형을 그릴 수 있고, 금광 2개를 선택하는 경우는 O(N^2) 으로 가능하다!

 

2) 선분 S가 있고, 그 위에 값들이 있을 때 다음과 같은 식이 성립한다.

먼저, 4개의 용어를 정의하겠다.

 

 sum = 선분 위에 있는 모든 값들의 합

 lsum = 선분의 맨 왼쪽에 있는 값부터 시작해서 연속된 최대 합

 rsum = 선분의 맨 오른쪽에 있는 값부터 시작해서 연속된 최대 합

 maxsum = 선분에서 얻을 수 있는 연속된 최대합

 

 그 후, 선분 S를 선분 L(left)와 선분 R(right)로 나눈 상황에서 선분 S의 sum, lsum, rsum, maxsum 을 어떻게 구할 수 있을지 생각해보자.

 

[sum]

 선분 S의 모든 값들의 합 = 선분 L의 모든 값의 합 + 선분 R의 모든 값의 합 이 성립한다.

 즉, Ssum = Lsum + Rsum 이 성립하고 이는 설명이 필요 없으니 넘어가겠다.

 

[lsum]

 선분 S의 맨 왼쪽부터 시작해서 연속된 최대 합에 대해서 생각해보자.

 선분 S의 맨 왼쪽에서 시작해서 연속된 최대 합은 선분 L의 범위에서 끝날 수도 있고, 선분 L의 범위를 다 포함하며 선분 R의 범위에서 끝날 수도 있다. 

 선분 L의 범위에서 끝났다면 그건 Llsum 이랑 동일하고, 선분 R의 범위에서 끝났다면 선분 L의 범위 값들을 다 합한 값과 Rlsum 을 합한 값이 될 것이다.

 즉, Slsum = max( Llsum, Lsum + Rlsum ) 이 성립한다.

 

[rsum]

 lsum과 마찬가지로 선분 S의 맨 오른쪽부터 시작해서 연속된 최대 합은 다음과 같다.

 Srum = max( Rrsum, Lrsum + Rsum )

 

[maxsum]

 이제 우리가 최종적으로 원하는 maxsum에 대해서 생각해보자. 선분 S에서 연속된 최대 합은 4개로 나눌 수 있다. 첫 번째는 선분 S에 있는 모든 값들을 다 합하는게 최대 합일 수가 있다. 또, 선분 L 범위에서 연속된 최대 합이 나오거나, 선분 R 범위에서 연속된 최대 합이 나오거나 아니면 마지막으로 선분 L과 R를 걸쳐서 연속된 최대 합이 나올 수 있다. 선분 L과 R을 걸쳐서 연속된 최대 합이 나오는 경우는 선분 L의 오른쪽에서 시작한 최대 합과 선분 R의 왼쪽에서 시작한 최대합을 연결한 값이 된다.

 따라서, Smaxsum = max ( Ssum , Lmaxsum, Rmaxsum, Lrsum + Rlsum ) 이 성립한다.

 

3) 이제, 1) 과 2) 를 이용해 문제를 해결해보자.

 1)에 의해 우리는 금광 2개를 정하면 직사각형을 정할 수 있다.

 --> 우리는 금광들의 y값 중에 2개를 선택해 먼저, 직사각형의 y 범위를 지정할 것이다.

 

 예제를 통해서 생각해보자.

 위와 같은 예시에서 y의 범위를 [2, 3] 으로 2개 선택해 지정한다면 우리는 (3, 3) / (7, 3) / (10, 2) 금광 3개를 생각해볼 수 있다. 이 금광들을 그냥 x축으로 내려서 (3) / (7) / (10) 에 있다고 생각을 하고 3에 있는 금광은 cost가 -1, 7에 있는 금광은 cost가 -1, 10에 있는 금광은 cost가 5 이므로 문제를 단순화시켜서 x축 위에 있는 금광들의 연속된 최대 합에 대해서 생각해보면 된다.

 즉, y를 2개 선택해서 범위를 지정하고 해당 범위에 있는 금광들을 다 x축으로 내린 다음에 2) 의 정의를 이용해 x축 구간의 연속된 최대 합을 구할 수 있다. 그러면 이는 직사각형을 그려서 최대 이익을 구하는 것과 동일하다.

 마지막으로, 구간의 연속된 최대 합이므로 자료구조 세그먼트 트리에 2) 공식을 적용해서 구하면 된다.

[ 코드 C++ ]

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define ll long long
 
using namespace std;
 
struct Point {
    int x, y, w;
};
 
struct Tree {
    ll lsum, rsum, sum, maxsum;
};
 
int N, leaf_size;
ll res = 0;
vector<int> x, y;
vector<Point> p;
Tree t[8192];
 
bool cmp(Point a, Point b) {
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
 
void clear(void) {
    for (int i = 0; i < 8192; i++)
        t[i].lsum = t[i].rsum = t[i].sum = t[i].maxsum = 0;
}
 
void update(int n, int w) {
    int c = leaf_size + n;
    t[c].lsum = t[c].rsum = t[c].sum = t[c].maxsum += w;
    while (c > 1) {
        c /= 2;
        int l = 2 * c, r = 2 * c + 1;
        t[c].sum = t[l].sum + t[r].sum;
        t[c].lsum = max(t[l].lsum, t[l].sum + t[r].lsum);
        t[c].rsum = max(t[r].rsum, t[l].rsum + t[r].sum);
        t[c].maxsum = max(max(t[l].rsum + t[r].lsum, t[c].sum), max(t[l].maxsum, t[r].maxsum));
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N;
    leaf_size = 1 << ((int)ceil(log2(N)));
 
    for (int i = 0, j, k, l; i < N; i++) {
        cin >> j >> k >> l;
        p.push_back({ j, k, l });
        x.push_back(j);
        y.push_back(k);
    }
    // 좌표압축과정
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    y.erase(unique(y.begin(), y.end()), y.end());
 
    for (int i = 0; i < p.size(); i++) {
        p[i].x = lower_bound(x.begin(), x.end(), p[i].x) - x.begin();
        p[i].y = lower_bound(y.begin(), y.end(), p[i].y) - y.begin();
    }
    sort(p.begin(), p.end(), cmp);
 
    // 이제 y값 후보 중에서 2개를 뽑는 모든 경우에서 최대로 얻을 수 있는 이득을 계산하자!
    for (int i = 0; i < y.size(); i++) {
        clear();
        int k = 0;
        while (k < p.size() && p[k].y < i)
            k++;
        for (int j = i; j < y.size(); j++) {
            while (k < p.size() && i <= p[k].y && p[k].y <= j) {
                update(p[k].x, p[k].w);
                k++;
            }
            res = max(res, t[1].maxsum);
        }
    }
    cout << res << '\n';
    return 0;
}
 cs

https://github.com/travelbeeee/BOJ/blob/master/BOJ10167.cpp

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 10282 : Failing Components  (0) 2020.08.21
[BOJ] 2517 : 달리기  (0) 2020.08.14
[BOJ] 1194 : 달이 차오른다, 가자.  (0) 2020.08.07
[BOJ] 17025 : Icy Perimeter  (0) 2020.07.30
[BOJ] 15898 : 피아의 아틀리에 ~신비한 대회의 연금술사~  (0) 2020.07.27

+ Recent posts

티스토리툴바