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

그리디 그리디알고리즘 우선순위큐

[ 문제해석 ]

 N개의 보석과 K개의 가방이 있다. 보석은 크기와 가치가 있고, 가방도 크기가 있다. 가방에는 최대 한 개의 보석만 넣을 수 있고, 가방 크기보다 큰 보석은 넣을 수 없다. 이때, 최대로 얻을 수 있는 가치는 얼마인가 를 구해야되는 문제다.

 

[ 알고리즘풀이 ]

 문제를 그리디하게 접근하면 쉽게 해결 할 수 있다.

 1) 현재 크기가 C인 가방이 있다고 하자. 단순하게 이 가방에 담을 수 있는 보석 중에 가장 가치가 큰 보석을 담는 것이 최대 가치를 얻을 수 있을 것이다.

 하지만, K개의 가방마다 N개의 보석을 순회하며 담을 수 있는 보석 중 가장 가치가 큰 보석을 찾는다면 시간 복잡도가 O(N * K) 가 되어 시간초과에 직면하게 된다. 

 

 2) 현재 크기가 C1인 가방과 C2인 가방이 있고 C2인 가방이 더 크다고 해보자. (C1 < C2)

 그러면 우리는 먼저 C1가방에 담을 수 있는 보석을 구해놓는다면 C2 가방에 담을 수 있는 보석은 C1보다 크기가 크므로 기존에 구해놓은 C1 가방에 담을 수 있는 보석에 추가로 C1 보다 크면서 C2보다 작거나 같은 보석들을 추가로 순회하면 된다. 따라서 보석과 가방이 크기 순으로 sorting 되어있다면 보석과 가방을 한 번 순회하며 문제를 해결 할 수 있다. 즉, 우리는 O(N + K) 로 문제를 해결 할 수 있다.

 

 --> 보석과 가방을 sorting 해놓는다.

 --> 현재 담을 수 있는 보석 중 가장 가치가 큰 보석을 찾아야되므로 priority_queue를 이용한다.

 --> 현재 가방에서 담을 수 있는 보석을 다 priority_queue에 넣고, 가장 가치가 큰 값을 가방에 담는다.

 --> 그 다음 가방에서는 현재까지 순회한 보석 뒤부터 다시 순회를 시작해서 추가로 담을 수 있는 보석을 priority_queue에 담아주고 마찬가지로 가장 가치가 큰 값을 가방에 담는다.

 --> 위 과정을 반복하면 된다.

 

[ 코드구현 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
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N, K;
pair<int, int> jewelries[300000];
int bags[300000];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> jewelries[i].first >> jewelries[i].second;
    for (int i = 0; i < K; i++)
        cin >> bags[i];
 
    sort(jewelries, jewelries + N);
    sort(bags, bags + K);
 
 
    priority_queue<int> pq;
    int jewelry = 0;
    long long ans = 0;
 
    for (int i = 0; i < K; i++) {
        for (int j = jewelry; j < N; j++) {
            if (jewelries[j].first > bags[i]) break; // 지금 가방에 못 넣는 보석!
            pq.push({ jewelries[j].second });
            jewelry++;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << '\n';
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1202.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02
[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26

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

BFS탐색

[ 문제해석 ]

 

 공기에 닿은 치즈가 녹는 문제로 언제 치즈가 다 녹는지를 구하면 된다.

 이때, 치즈를 녹이는 건 간단하다
 '1'(치즈)를 만나면 치즈의 위 아래 왼쪽 오른쪽을 탐색해 '0' 이 있으면 치즈는 녹는다!
 하지만, 모든 '0' 이 치즈를 녹일 수는 없다. 치즈 안에 갇혀있는 '0'(구멍) 이라면 치즈를 녹일 수 없다.
--> 따라서, 우리는 '0' 들을 구멍인지 아닌지 먼저 탐색을 진행해야한다.

--> 치즈에 갇혀있는 '0' 이라는건 치즈 밖에서 탐색을 진행했을 때, 탐색할 수 없는 '0'이다.
--> Map의 테두리는 무조건 치즈가 올 수 없다 했으므로 우리는 map[0][0] 은 무조건 '0' 인 것을 안다.
--> map[0][0] 에서 탐색을 시작해서 방문할 수 있는 '0'을 다 방문하자!
--> 이때, 방문할 수 있는 '0' 들은 치즈에 갇혀있지 않으므로 구멍이 아니다!

 

[ 알고리즘풀이 ]

 

1) Map을 순회하며 현재 치즈를 count 한다. --> 현재 Map에 치즈가 없다면 다 녹은 상태! 알고리즘 종료!
2) map[0][0] 에서 BFS 탐색을 진행해 구멍이 아닌 '0' 들을 다 체크한다.
3) Map을 순회하며 치즈들을 녹인다.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<queue>
 
using namespace std;
 
int r, c, map[100][100];
bool isHole[100][100];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
 
bool isInside(int x, int y) {
    return (0 <= x && x < r && 0 <= y && y < c);
}
 
int getCheese(void) {
    int res = 0;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            if (map[i][j] == 1) res++;
    return res;
}
 
void checkHole(void) {
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            isHole[i][j] = true;
 
    queue<pair<int, int>> q;
    bool visited[100][100] = {};
 
    q.push({ 0, 0 });
    isHole[0][0] = false;
    visited[0][0] = true;
 
    while (!q.empty()) {
        int curX = q.front().first, curY = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = curX + dx[i], nextY = curY + dy[i];
            if (!isInside(nextX, nextY)) continue;
            if (visited[nextX][nextY]) continue;
            if (map[nextX][nextY] == 1) continue;
            visited[nextX][nextY] = 1;
            isHole[nextX][nextY] = false;
            q.push({ nextX, nextY });
        }
    }
 
    return;
}
 
void meltingCheese(void) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] == 1) { // 치즈가 녹는지 체크하자!
                for (int k = 0; k < 4; k++) {
                    int nextX = i + dx[k], nextY = j + dy[k];
                    if (isInside(nextX, nextY) && map[nextX][nextY] == 0 && !isHole[nextX][nextY]) {
                        map[i][j] = 0;
                        break;
                    }
                }
            }
        }
    }
    return;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++)
            cin >> map[i][j];
 
    int time = 0, cheese;
    while (1) {
        int curCheese = getCheese();
        if (!curCheese) break; // 현재 cheese가 없으면 끝!
 
        checkHole(); // 구멍인 '0' 아닌 '0'을 따로 체크!
        meltingCheese(); // 치즈를 녹이자
 
        cheese = curCheese;
        time++;
    }
    cout << time << '\n' << cheese << '\n';
 
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ2636.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02
[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25

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

에라토스테네스체 소수 골드바흐의추측 정수론

[ 알고리즘풀이 ]

 

 우리는 A + B가 두 소수의 합으로 표현되는지 판단해야된다. ( A + B 를 S 라고 표현하겠다 )

 1) S 가 짝수인 경우

 --> 골드바흐가 짝수인 수는 '2'를 제외하고 모두 두 소수의 합으로 표현이 가능하다고 추측했고, 10^18 이하의 숫자에 대해서는 해당 추측이 참이라고 증명이 됐다.

 --> '2'를 제외하고 S가 짝수인 경우는 두 소수의 합으로 표현 할 수 있다!

 --> '2' 는 두 소수의 합으로 표현이 불가능하다

 

 2) S 가 홀수인 경우

 --> 홀수는 짝수 + 홀수로만 표현이 가능하다. 즉, 짝수 소수 + 홀수 소수로 표현이 가능한지 아닌지 판단하면 된다.

 --> 짝수 소수는 '2' 밖에 없으므로 우리는 ( S - 2 ) 가 소수인지 아닌지 판단하면 된다.

 --> S가 최대 4 * 10^12 이므로 우리는 route(4 * 10^12) 인 2 * 10^6 이하의 소수만 알고있으면 S가 큰 값이 들어오더라도 소수인지 아닌지 판단이 가능하다.

 --> 따라서 에라토스테네스 체를 이용해 2 * 10^6 이하의 소수들을 다 구해놓고 ( S - 2 ) 가 2 * 10^6 보다 작다면 에라토스테네스 체로 바로 소수인지 판단하고, 2 * 10^6 보다 크다면 에라토스테네스 체로 구해놓은 소수들로 다 나누어보면 된다.

 

[ 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>
#include<vector>
 
using namespace std;
 
const int MAX_LENGTH = 2000000;
vector<int> prime;
bool eratos[MAX_LENGTH + 1];
 
void eratosthenes(void) { // 에라토스테네스체로 2백만 이하의 모든 소수를 구하자 false면 소수
    eratos[0] = eratos[1] = true;
    for (int i = 2; i <= MAX_LENGTH; i++) {
        if (eratos[i] == false) {
            prime.push_back(i);
            for (int j = i * 2; j <= MAX_LENGTH; j += i)
                eratos[j] = true;
        }
    }
}
 
bool isPrime(long long A) {
    if (A <= MAX_LENGTH) return !eratos[A];
    else{
        for (int i = 0; i < prime.size(); i++)
            if ( A % prime[i] == 0)
                return false;
        return true;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    eratosthenes();
 
    int T;
    cin >> T;
    while (T--) {
        long long A, B, S;
        cin >> A >> B;
        S = A + B;
        if (S == 2) cout << "NO\n";
        else if (S % 2 == 0) cout << "YES\n"; // 골드바흐의추측
        else { // S가 홀수라면 --> 짝수 + 홀수 꼴만 가능 --> 짝수 소수는 2 밖에 없음
            if (isPrime(S - 2)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ15711.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 1826 : 연료 채우기  (1) 2020.08.26
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25

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

그리디 탐색

[ 문제해석 ]

 

 아래와 같은 2가지 이유 때문에 연료를 중심으로 그리디하게 접근해야 된다.

 

 1) 현재 가지고 있는 연료 = 현재 내가 갈 수 있는거리

 내가 현재 나갈 수 있는 거리는 내 거리에서 가지고 있는 연료만큼 이동할 수 있다. 따라서, 연료랑 내가 갈 수 있는 거리는 동일한 의미로 해석할 수 있다!

 

 2) 주유소 연료 + 현재 가지고 있는 연료 = 주유소 들려서 갈 수 있는 거리

 내가 현재 가지고 있는 연료로 갈 수 있는 주유소가 K개 있다고 해보자. 어차피 K개의 주유소는 내가 지금 다 들릴 수 있고 우리는 도착 지점까지 주유소를 적게 들리고 이동해야 한다.

 --> 이왕 주유소에 들릴 거면 들렸을 때 가장 멀리 갈 수 있는 주유소에 들리는 게 좋다!

 --> 주유소에서 얻을 수 있는 연료 + 내가 가지고 있는 연료 = 주유소에 들려서 갈 수 있는 거리이므로 들릴 수 있는 주유소 중에서 연료가 제일 많은 곳이 의미가 있다!

 

예를 들어, 내가 연료가 10인 상태에서 시작하고 (2,4) / (6,5) 에 주유소가 있다고 하자. 
(2, 4) 주유소는 연료를 2만 쓰고 4를 얻을 수 있고, 
(6, 5) 주유소는 연료를 6이나 쓰고 5를 얻을 수 있으므로 (2,4) 가 더 유리해 보인다.
--> 이게 함정!! 
(2, 4) 를 들리면 연료가 12가 남고 (6, 5) 를 들리면 연료가 9 가 남지만  
실제로 (2, 4)를 들리면 나는 최대 14까지 갈 수 있고 (6, 5)를 들리면 나는 최대 15까지 갈 수 있음 
--> 내가 갈 수 있는 주유소 중에서 연료를 제일 많이 주는 주유소들을 계속 탐색해야됨! 

 

[ 알고리즘풀이 ]

 

 L = 도착지점

 curL = 현재 연료양 = 현재 갈 수 있는 거리

 ans = 주유소 들린 횟수

 curP = 현재 연료양으로 갈 수 있는 주유소 인덱스

  

 0) 현재 연료양으로 도착지점에 갈 수 있는지 체크한다. (curL < L)

 1) 도착할 수 없다면, priority_queue 를 이용해서 현재 갈 수 있는 주유소의 연료를 다 push한다.

 2) 우리는 어차피 갈 수 있는 주유소 중에서 연료를 제일 많이 주유소가 필요!

 --> 가장 연료를 많이 주는 주유소를 들리자.
 --> curL += pq.top(); ( 가장 많이 주는 주유소에 들려 연료 충전! )

 --> ans++;  ( 주유소에 방문함 )

 3) 0~2) 과정을 반복한다! 이때, 모든 주유소를 방문해봐서 priority_queue 가 비었는데도 도착지점에 도착할 수 없다면 -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
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int N, L, P;
    pair<int, int> gasStation[10000];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> gasStation[i].first >> gasStation[i].second;
    cin >> L >> P;
 
    sort(gasStation, gasStation + N);
 
    // P연료를 가지고 L까지 가야된다!
    priority_queue<int> pq;
 
    int curP = 0, curL = P, ans = 0;
    while (curL < L) {
        while (curP < N && gasStation[curP].first <= curL) {
            pq.push(gasStation[curP++].second);
        }
        if (pq.empty()) { // L 에 도착도 못했고, 더 이상 갈 곳도 없음.
            ans = -1;
            break;
        }
        curL += pq.top();
        pq.pop();
        ans++;
    }
    cout << ans << '\n';
    return 0;
}
 cs

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1826.cpp

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27
[BOJ] 9881 : Ski Course Design  (0) 2020.08.25
[BOJ] 13711 : LCS 4  (0) 2020.08.25
[BOJ] 2632 : 피자판매  (0) 2020.08.24

+ Recent posts

티스토리툴바