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

누적합

[ 알고리즘풀이 ]

 문제 Input 크기를 유심히 들여다보면 쉽게 해결할 수 있는 문제다.

 최대 피자 조각이 1000개이므로 우리는 피자 조각이 연속된 합을 모두 구해보아도 O(N^2) 으로 시간 초과에 걸리지 않는다. 또한, 피자 조각의 크기가 최대 1000이므로 연속된 합이 1000 * 1000 을 넘어가지 않으므로, 10^6 크기의 int 배열로 가능한 모든 피자 조각의 연속된 합을 count 할 수 있다.

 A / B 피자별로 가능한 모든 피자 조각의 연속된 합을 count 하고 난 후, client 가 원하는 크기를 A와 B 피자에서 조각을 꺼내와 만들면 답을 쉽게 구할 수 있다.

 

[ 코드 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
#include<iostream>
 
using namespace std;
 
int client, nA, nB;
int pizzaA[1000], pizzaB[1000]; // pizza 조각들
int sizeA[1000001] = {}, sizeB[1000001] = {}; // pizza 조각으로 만들 수 있는 크기 count
int ans = 0;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> client >> nA >> nB;
    for (int i = 0; i < nA; i++)
        cin >> pizzaA[i];
    for (int i = 0; i < nB; i++)
        cin >> pizzaB[i];
 
    sizeA[0] = 1, sizeB[0] = 1; 
    int sum = 0;
    for (int i = 0; i < nA; i++)
        sum += pizzaA[i];
    sizeA[sum]++;
    sum = 0;
    for (int i = 0; i < nB; i++)
        sum += pizzaB[i];
    sizeB[sum]++;
 
    for (int i = 0; i < nA; i++) {
        int sum = 0;
        for (int j = 0; j < nA - 1; j++) {
            sum += pizzaA[(i + j) % nA];
            sizeA[sum]++;
        }
    }
    for (int i = 0; i < nB; i++) {
        int sum = 0;
        for (int j = 0; j < nB - 1; j++) {
            sum += pizzaB[(i + j) % nB];
            sizeB[sum]++;
        }
    }
    // client 가 원하는 조각을 몇 개 만들 수 있는지 count 해준다.
    for (int i = 0; i <= client; i++)
        ans += (sizeA[i] * sizeB[client - i]);
 
    cout << ans << '\n';
}
 cs

[ github ]

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

 

travelbeeee/BOJ

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

github.com

 

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

[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 11964 : Fruit Feast  (0) 2020.08.23
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21

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

BFS 그래프탐색

[ 문제풀이 ]

 레몬과 오렌지를 먹어서 배부름 정도를 최대로 만들고 싶은데, 이때 물을 중간에 한 번 먹어서 배부름 정도를 절반으로 낮출 수 있다. 레몬과 오렌지의 배부름 정도는 A, B이고 내 최대 배부름은 T이므로 T를 넘지 않는 선에서 레몬과 오렌지를 먹어 만들 수 있는 최대 배부름을 구하자.

 

[ 알고리즘풀이 ]

 ( 배부름 정도, 물을 먹었는지 ) 2개의 값을 가지고 ( 0, 0) 에서 시작해서 BFS 탐색을 진행하면 된다.

 

[ 코드 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
#include<iostream>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int T, A, B, ans = -1;
    bool visited[500001][2] = {};
 
    cin >> T >> A >> B;
 
    queue<pair<int, bool>> q;
    q.push({ 0, 0 });
    visited[0][0] = 1;
    while (!q.empty()) {
        int curF = q.front().first;
        bool drinkWater = q.front().second;
        q.pop();
 
        ans = max(ans, curF);
 
        if (curF + A <= T && !visited[curF + A][drinkWater]) {
            q.push({ curF + A, drinkWater });
            visited[curF + A][drinkWater] = 1;
        }
        if (curF + B <= T && !visited[curF + B][drinkWater]) {
            q.push({ curF + B, drinkWater });
            visited[curF + B][drinkWater] = 1;
        }
        if (!drinkWater && !visited[curF / 2][!drinkWater]) {
            q.push({ curF / 2, !drinkWater });
            visited[curF / 2][!drinkWater] = 1;
        }
    }
    cout << ans << '\n';
 
    return 0;
}
 cs

[ gitHub ]

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

 

travelbeeee/BOJ

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

github.com

 

 

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

[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24
[BOJ] 18808 : 스티커 붙이기  (0) 2020.08.23
[BOJ] 10282 : Failing Components  (0) 2020.08.21
[BOJ] 2517 : 달리기  (0) 2020.08.14

문제 : 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

+ Recent posts

티스토리툴바