문제 : www.acmicpc.net/problem/17404

DP DynamicProgramming

[ 문제해석 ]

 

 N개의 집에 빨, 초, 파 중 하나의 색깔을 칠할건데 i번 째 집은 (i - 1)번 집, (i + 1)번 집과 색깔이 달라야 한다. 또, 첫 번째 집은 두 번째 집과 마지막 집과 색깔이 달라야된다. (원형)

 이때, 각 집마다 빨, 초, 파 색깔을 칠하는 cost가 주어진다면 모든 집들을 색칠하는데 드는 최소 비용은 얼마일까.

 

[ 알고리즘풀이 ]

 

 1) 점화식

dp[i][0] := (i -1)번 째 집까지 색칠을 다한 상황에서

              i 번 째 집을 0(빨간)색으로 칠할 때 최소 비용 이라고 정의

 

--> i번 째 집을 0(빨간)으로 칠하므로 (i - 1)번 째 집은 1(초록) 혹은 2(파랑) 으로 칠한 상황 중에 더 작은 값을 선택하면 된다.

--> dp[i][0] = color[i][0] + min(dp[i - 1][1], dp[i - 1][2] ) 성립!


다른 dp[i][1], dp[i][2] 도 마찬가지다

 

 2) 원형

우리는 첫 번째 집이 마지막 집에 영향을 끼치는 원형 문제다.
--> 첫 번째 집을 빨 / 초 / 파 3가지 경우로 각각 칠해서 각각 dp 배열을 구해본다.
--> 첫 번째 집을 빨로 칠하면 dp 배열을 채우고, 마지막 집을 초 / 파로 선택한 값들만 사용한다.
--> 마찬가지로 첫 번째 집을 초, 파로 칠하고 점화식을 이용해 dp배열을 채운 후 마지막 집을 다른 색깔로 선택한 값들만 이용한다.

 

[ 코드 구현 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
#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
const int INF = 99999999;
int N, color[1000][3], ans = INF;
int dp[1000][3];
 
void getCost(void) {
    for (int i = 2; i < N; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + color[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + color[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + color[i][2];
    }
    return;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    
    // 빨간집에서 시작했다고 가정하고 dp배열을 채워보자.
    dp[1][0] = INF, dp[1][1] = color[0][0] + color[1][1], dp[1][2] = color[0][0] + color[1][2];
    getCost();
    ans = min(ans, min(dp[N - 1][1], dp[N - 1][2]));
 
    // 초록집에서 시작했다고 가정하고 dp배열을 채워보자
    memset(dp, 0, sizeof(dp));
    dp[1][0] = color[0][1] + color[1][0], dp[1][1] = INF, dp[1][2] = color[0][1] + color[1][2];
    getCost();
    ans = min(ans, min(dp[N - 1][0], dp[N - 1][2]));
 
    // 파란집에서 시작햇다고 가정하고 dp배열을 채워보자
    memset(dp, 0, sizeof(dp));
    dp[1][0] = color[0][2] + color[1][0], dp[1][1] = color[0][2] + color[1][1], dp[1][2] = INF;
    getCost();
    ans = min(ans, min(dp[N - 1][0], dp[N - 1][1]));
 
    cout << ans << '\n';
 
    return 0;
}
 cs

[ github ]

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

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 14226 : 이모티콘  (0) 2020.09.15
[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 9576 : 책 나눠주기  (0) 2020.09.02
[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 2636 : 치즈  (0) 2020.08.27

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

그리디 그리디알고리즘

[ 알고리즘풀이 ]

 그리디하게 문제를 해결 할 수 있다.

 (a1, b1) (a2, b2) .... (aM, bM) 신청서가 있다고 할 때, b값이 작고 b값이 같다면 a값이 작은 신청서들을 먼저 처리해주면 된다.

 

 1) 주어진 학생들의 신청서(a,b)를 b가 더 작고 b가 같다면 a가 더 작은 순으로 정렬한다.

 2) 정렬된 신청서를 순회하며 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
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        int N, M, ans = 0;
        pair<int, int> list[1000];
        bool checked[1001] = {};
 
        cin >> N >> M;
        for (int i = 0; i < M; i++)
            cin >> list[i].second >> list[i].first;
 
        sort(list, list + M);
 
        for (int i = 0; i < M; i++) {
            for(int j = list[i].second; j <= list[i].first; j++)
                if (!checked[j]) {
                    checked[j] = true;
                    break;
                }
        }
 
        for (int i = 1; i <= N; i++)
            if (checked[i]) ans++;
 
        cout << ans << '\n';
 
    }
}
 cs

[ github ]

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

 

travelbeeee/ProblemSolving

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

github.com

 

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

[BOJ] 1107 : 리모컨 고치기  (0) 2020.09.14
[BOJ] 17404 : RGB거리 2  (0) 2020.09.03
[BOJ] 1202 : LOPOV  (0) 2020.08.28
[BOJ] 2636 : 치즈  (0) 2020.08.27
[BOJ] 15711 : 환상의 짝궁  (0) 2020.08.27

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

+ Recent posts

티스토리툴바