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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

<풀이>

1. 구역의 정보를 입력받는다.

2. 조건에 맞게 구역들을 두 개의 선거구에 포함시키고, 두 선거구간 인구 차이의 최솟값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우를 다 해보아야합니다. 따라서, 저는 브루트포스를 선택하였습니다. 하지만, 여기서 한번 멈칫했습니다. 구역들은 한 선거구가 되려면 모두 연결되어있어야합니다. 그러면 이 조건을 (1)구역들을 뽑을 때 검사해야하나 (2)구역을 다 나눠놓고 검사해도되나 망설여집니다. 저는 시간복잡도를 따져보았습니다. 구역은 10개 이하로 주어지므로, 연산횟수는 1024회 입니다. 따라서, 저는 (2)를 선택했습니다.

 

2. 구역들이 모두 연결되어있는지 확인하기

=> 구역들을 두 개로 나누었다면, 같은 선거구의 구역들이 모두 연결되어있는지 확인해야 합니다. 저는 BFS를 이용해서 조건을 확인했습니다.

 

3. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다. 구역들을 두 선거구로 나누는 모든 경우를 해본다.

(2) 두 선거구로 나누었으면, ①두 선거구에 구역들이 하나라도 포함되어있는지 확인하고, ②같은 선거구에 있는 구역들이 모두 연결되어있는지 확인합니다. 

(3) 두 선거구간 인구차이의 최소를 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

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 <string.h>
#include <queue>
#include <vector>
#define INF 987654321
 
using namespace std;
 
int N;
int people[11];
bool edge[11][11];
vector<int> a, b;
int answer;
 
bool isLinked(vector<int> sector) {
    queue<int> q;
    bool visited[11];
    memset(visited, false, sizeof(visited));
 
    int start = sector.front();
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < sector.size(); i++) {
            int nxt = sector[i];
            if (!visited[nxt] && edge[cur][nxt]) {
                q.push(nxt);
                visited[nxt] = true;
            }
        }
    }
 
    for (int i = 0; i < sector.size(); i++) {
        int node = sector[i];
        if (!visited[node]) return false;
    }
    return true;
}
 
int divideSector(int idx, int sumA, int sumB) {
    if (idx > N) {
        if (!sumA || !sumB) return INF;
        else {
            if (isLinked(a) && isLinked(b)) return abs(sumA - sumB);
            else return INF;
        }
    }
 
    int ret = INF;
    //a구역에 넣는 경우
    a.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA + people[idx], sumB));
    a.pop_back();
    //b구역에 넣는 경우
    b.push_back(idx);
    ret = min(ret, divideSector(idx + 1, sumA, sumB + people[idx]));
    b.pop_back();
    return ret;
}
 
void solution() {
    answer = divideSector(1, 0, 0);
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 0;
    memset(people, 0, sizeof(people));
    memset(edge, false, sizeof(edge));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> people[i];
    }
    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int node = 0;
            cin >> node;
            edge[i][node] = true;
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 BFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17406 - 배열 돌리기 4  (1) 2022.12.22
[C++] 백준 17281 - 야구(⚾)  (0) 2022.12.22
[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21

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

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

<풀이>

1. 배열 정보와 회전 정보를 입력받는다.

2. 회전순서를 정해서 배열을 돌리고, 얻을 수 있는 배열의 최솟값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 회전 순서에 따라 배열이 다 달라지므로, 모든 경우의 회전순서를 다 만들어서 시뮬레이션을 진행해야합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 시뮬레이션 구현하기

=> 회전순서를 정했으면, 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞는 정확한 구현입니다. 저는 배열을 돌릴때 Deque을 사용했습니다.

 

3. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다. 모든 경우의 회전순서를 만든다.

(2) 회전순서를 정했으면, 시뮬레이션을 진행한다.(배열을 돌릴 때 덱을 사용한다)

(3) 배열의 최솟값을 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <string.h>
#include <algorithm>
#include <deque>
#define INF 987654321
 
using namespace std;
 
int N, M, K;
int A[51][51];
int A_copy[51][51];
int R[6], C[6], S[6];
int order[6];
bool visited[6];
int answer;
 
void rotate(int x1, int y1, int x2, int y2) {
    deque<int> dq;
    //숫자 담기
    for (int i = y1; i < y2; i++) dq.push_back(A_copy[x1][i]);
    for (int i = x1; i < x2; i++) dq.push_back(A_copy[i][y2]);
    for (int i = y2; i > y1; i--) dq.push_back(A_copy[x2][i]);
    for (int i = x2; i > x1; i--) dq.push_back(A_copy[i][y1]);
    //순서 바꾸기
    dq.push_front(dq.back());
    dq.pop_back();
    //숫자 순서대로 놓기
    for (int i = y1; i < y2; i++) {
        A_copy[x1][i] = dq.front(); dq.pop_front();
    }
    for (int i = x1; i < x2; i++) {
        A_copy[i][y2] = dq.front(); dq.pop_front();
    }
    for (int i = y2; i > y1; i--) {
        A_copy[x2][i] = dq.front(); dq.pop_front();
    }
    for (int i = x2; i > x1; i--) {
        A_copy[i][y1] = dq.front(); dq.pop_front();
    }
}
 
void copyA() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            A_copy[i][j] = A[i][j];
        }
    }
}
 
void simulation() {
    //1. 맵 복사
    copyA();
    //2. 순서에 따라 배열 돌리기
    for (int i = 0; i < K; i++) {
        int o = order[i];
        int r = R[o], c = C[o], s = S[o];
        for (int j = 0; j < s; j++) {
            rotate(r - s + j, c - s + j, r + s - j, c + s - j);
        }
    }
}
 
int rowSum(int col) {
    int output = 0;
    for (int i = 1; i <= M; i++) {
        output += A_copy[col][i];
    }
    return output;
}
 
int minRowSum() {
    int output = INF;
    for (int i = 1; i <= N; i++) {
        output = min(output, rowSum(i));
    }
    return output;
}
 
int selectOperOrder(int cnt) {
    if (cnt == K) {
        simulation();
        return minRowSum();
    }
 
    int ret = INF;
    for (int i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            order[cnt] = i;
            ret = min(ret, selectOperOrder(cnt + 1));
            visited[i] = false;
        }
    }
    return ret;
}
 
void solution() {
    answer = selectOperOrder(0);
}
 
int main() {
    //초기화
    N = 0, M = 0, K = 0;
    memset(A, 0, sizeof(A));
    memset(R, 0, sizeof(R));
    memset(C, 0, sizeof(C));
    memset(S, 0, sizeof(S));
    memset(order, 0, sizeof(order));
    memset(visited, false, sizeof(visited));
    answer = 0;
 
    //입력
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < K; i++) {
        cin >> R[i] >> C[i] >> S[i];
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17471 - 게리맨더링  (0) 2022.12.22
[C++] 백준 17281 - 야구(⚾)  (0) 2022.12.22
[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21

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

 

17281번: ⚾

⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종

www.acmicpc.net

<풀이>

1. 이닝 별 선수 타격을 입력받는다.

2. 1번 타자를 4번으로 고정했을 때, 타순을 잘 정해서 팀이 얻을 수 있는 최대 점수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 1번 타자를 4번으로 고정하고, 모든 경우의 타선을 다 해보아야합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 시뮬레이션 구현하기

=> 타순이 정해졌으면, 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞는 정확한 구현입니다. 저는 시뮬레이션 구현에서 타선을 Queue로 구현하였습니다.

 

3. 구현 전 총정리

=> 아래는 저가 구현 전에 정리한 생각입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 모든 경우의 타선을 만들어본다.

(2) 타선이 완성됐으면, 시뮬레이션을 진행한다.(타선은 큐로 구현한다)

(3) 얻을 수 있는 최대 점수를 return한다.

자세한 구현은 아래 코드를 참조해주세요.

 

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
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int N;
int record[50][9];
int order[9];
bool visited[9];
int answer;
 
int getPoint(int hit, bool base[]) {
    int output = 0;
 
    base[0] = true;
    for (int i = 3; i >= 0; i--) {
        if (base[i]) { //주자가 있을 경우
            if (i + hit > 3) {  //홈인
                base[i] = false;
                output++;
            }
            else { //진루
                base[i] = false;
                base[i + hit] = true;
            }
        }
    }
    return output;
}
 
int simulation() {
    int output = 0;    
    int inning = 0;
    queue<int> q; //타선을 큐로 구현
    for (int i = 0; i < 9; i++) {
        q.push(order[i]);
    }
    
    while (inning < N) {
        bool base[4];
        memset(base, false, sizeof(base));
        int out = 0;
 
        while (out != 3) {
            int hitter = q.front();
            q.pop();
            
            int hit = record[inning][hitter];
            if (hit == 0) out++;
            else output += getPoint(hit, base);
            
            q.push(hitter);
        }
        inning++;
    }
 
    return output;
}
 
int ordering(int idx) {
    if (idx == 9) {
        return simulation();
    }
 
    int ret = 0;
    if (idx == 3) ret = ordering(idx + 1);
    else {
        for (int i = 0; i < 9; i++) {
            if (!visited[i]) {
                order[idx] = i;
                visited[i] = true;
                ret = max(ret, ordering(idx + 1));
                visited[i] = false;
            }
        }
    }
    return ret;
}
 
void solution() {
    visited[0] = true;
    order[3] = 0;
    answer = ordering(0);
}
 
int main() {
    //초기화
    N = 0;
    memset(record, 0, sizeof(record));
    memset(order, 0, sizeof(order));
    memset(visited, false, sizeof(visited));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> record[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17471 - 게리맨더링  (0) 2022.12.22
[C++] 백준 17406 - 배열 돌리기 4  (1) 2022.12.22
[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21

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

 

17136번: 색종이 붙이기

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. <그림 1> 색종이를 크

www.acmicpc.net

<풀이>

1. 종이 상태를 입력받는다.

2. 종이의 모든 1을 덮는데 필요한 색종이의 최소 갯수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 큰 색종이부터 먼저 붙이는 그리디한 방식으로 불가능합니다. 왜냐하면, 6x6을 최소로 덮는 방법은 5x5를 사용하는 것이 아닌, 3x3을 사용하는 것이기 때문입니다. 그러므로, 색종이를 붙여야하는 곳에 5가지 색종이를 모두 붙여보아야 합니다. 따라서, 저는 브루트포스를 선택했습니다.

 

2. 구현 방법 떠올리기

=> 아래는 구현 전에 저가 미리 생각한 것입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다.

(2) 종이의 좌표를 순차적으로 탐색하면서, 1인 부분에 5가지 색종이를 모두 덮어본다.

(3) 종이를 모두 탐색하면 함수는 종료된다.

자세한 구현은 아래 코드를 참조해주세요.

 

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
#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int N;
int map[10][10];
bool covered[10][10];
int cnt[6];
int answer;
 
bool canCover(int x, int y, int length) {
    //종이를 다 쓴 경우
    if (cnt[length] == 5) return false;
    //범위 벗어난 경우
    if (x + length > N || y + length > N) return false;
    //0을 덮거나, 이미 덮여져 있는 경우
    for (int i = x; i < x + length; i++) {
        for (int j = y; j < y + length; j++) {
            if (map[i][j] == 0 || covered[i][j]) return false;
        }
    }
    return true;
}
 
void cover(int x, int y, int length, bool type) {
    for (int i = x; i < x + length; i++) {
        for (int j = y; j < y + length; j++) {
            covered[i][j] = type;
        }
    }
}
 
void getNxt(int& x, int& y) {
    if (y == 9) x++, y = 0;
    else y++;
}
 
int coverPaper(int x, int y, int sum) {
 
    if (x == N) return sum;
 
    int ret = INF;
    //색종이를 붙여야 하는 경우
    if (map[x][y] == 1 && !covered[x][y]) {
        for (int i = 1; i <= 5; i++) {
            if (canCover(x, y, i)) {
                cover(x, y, i, true);
                cnt[i]++;
                int nx = x, ny = y;
                getNxt(nx, ny);
                ret = min(ret, coverPaper(nx, ny, sum + 1));
                cover(x, y, i, false);
                cnt[i]--;
            }
        }
    }
    else {
        int nx = x, ny = y;
        getNxt(nx, ny);
        ret = coverPaper(nx, ny, sum);
    }
    return ret;
}
 
void solution() {
    answer = coverPaper(0, 0, 0);
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 10;
    memset(map, 0, sizeof(map));
    memset(covered, false, sizeof(covered));
    memset(cnt, 0, sizeof(cnt));
    answer = 0;
 
    //입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17406 - 배열 돌리기 4  (1) 2022.12.22
[C++] 백준 17281 - 야구(⚾)  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21
[C++] 백준 16637 - 괄호 추가하기  (0) 2022.12.21

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

 

17135번: 캐슬 디펜스

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

www.acmicpc.net

<풀이>

1. 격자판을 입력받는다.

2. 궁수 3명을 배치해서, 죽일 수 있는 적의 최대 수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 궁수 3명을 배치할 수 있는 모든 경우를 해보아야 합니다. 따라서, 저는 브루트포스를 선택해서 궁수를 모든 경우에 배치해보았습니다.

 

2. 시뮬레이션 구현하기

=> 궁수 3명을 배치한 이후에는 시뮬레이션을 진행해야합니다. 시뮬레이션의 핵심은 문제의 조건에 맞게 정확하게 구현하는 것입니다. 구현방법은 아래의 코드를 참조해주세요.

 

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
struct enemy {
    pos p;
    int dist;
};
 
int N, M, D;
int map[15][15];
int map_copy[15][15];
int archer[3];
int answer;
 
bool cmp(enemy e1, enemy e2) {
    if (e1.dist == e2.dist) {
        if (e1.p.y == e2.p.y) return e1.p.x < e2.p.x;
        return e1.p.y < e2.p.y;
    }
    return e1.dist < e2.dist;
}
 
int getDist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}
 
bool isNoEnemy(int col) {
    for (int i = 0; i < col; i++) {
        for (int j = 0; j < M; j++) {
            if (map_copy[i][j] == 1) return false;
        }
    }
    return true;
}
 
void copyMap() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map_copy[i][j] = map[i][j];
        }
    }
}
 
int countDeadEnemy() {
 
    int output = 0;
 
    //1. 시뮬레이션 맵 카피
    copyMap();
    int archerCol = N;
    //2. 시뮬레이션
    while (archerCol >= 1) {
        if (isNoEnemy(archerCol)) break;
        //(1) 모든 궁수마다 죽일 적 선택하기
        vector<pos> kill;
        for (int i = 0; i < 3; i++) {
            vector<enemy> v;
            //적 담기
            for (int j = 0; j < archerCol; j++) {
                for (int k = 0; k < M; k++) {
                    if (map_copy[j][k] == 1) {
                        int dist = getDist(archerCol, archer[i], j, k);
                        if (dist <= D) v.push_back({ {j,k},dist });
                    }
                }
            }
            //정렬
            sort(v.begin(), v.end(), cmp);
            //죽일 적 1명 담기
            if (!v.empty()) kill.push_back(v.front().p);
        }
        //(2) 적 죽이기
        for (auto& k : kill) {
            if (map_copy[k.x][k.y] == 1) {
                map_copy[k.x][k.y] = 0;
                output++;
            }
        }
        //(3) 궁수 라인 올리기
        archerCol--;
    }
 
    return output;
}
 
int selectArcherPos(int idx, int cnt) {
 
    if (cnt == 3) return countDeadEnemy();
 
    int ret = 0;
    for (int i = idx; i < M; i++) {
        archer[cnt] = i;
        ret = max(ret, selectArcherPos(i + 1, cnt + 1));
    }
    return ret;
}
 
void solution() {
    answer = selectArcherPos(0, 0);
}
 
int main() {
    //초기화
    N = 0, M = 0, D = 0;
    memset(map, 0, sizeof(map));
    memset(map_copy, 0, sizeof(map_copy));
    memset(archer, 0, sizeof(archer));
    answer = 0;
 
    //입력
    cin >> N >> M >> D;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

브루트포스와 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17281 - 야구(⚾)  (0) 2022.12.22
[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21
[C++] 백준 16637 - 괄호 추가하기  (0) 2022.12.21
[C++] 백준 13460 - 구슬 탈출2  (1) 2022.12.21

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

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의

www.acmicpc.net

<풀이>

1. 집의 상태를 입력받는다.

2. 파이프를 한쪽 끝으로 옮길 수 있는 방법의 수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 방법의 수를 구해야하므로, 파이프를 놓는 모든 경우를 다 해보아야합니다. 따라서, 저는 백트래킹을 선택하였습니다.(파이프를 놓을 수 있는 유망한 경우에만 탐색할 것이므로)

 

2. 파이프 옮기기

=> 파이프는 종류에 따라 (1)다음에 놓을 파이프가 다르고, (2)파이프를 놓을 수 있는 공간이 다릅니다. 따라서, 저는 위 두가지 경우를 배열로 미리 만들어 놓았습니다.(코드의 connect[][]와 check[][] 참조)

 

3. 최적화 할 수 있을까?

=> 이 문제는 작은 부분 문제에서 구한 최적의 답을 이용해서 큰 문제의 최적의 답을 구할 수 있습니다. 따라서, 저는 DP를 이용하여 최적화 하였습니다.

 

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
#include <iostream>
#include <string.h>
 
using namespace std;
 
int dx[] = { 0,1,1 };
int dy[] = { 1,0,1 };
int connect[3][3] = { //파이프 끼리 연결 가능 여부
    {1,0,1},          
    {0,1,1},
    {1,1,1},
};
int check[3][3] = { //파이프를 놓을 때, 확인해야하는 부분
    {1,0,0},
    {0,1,0},
    {1,1,1}
};
 
int N;
int map[16][16];
int cache[16][16][3];
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
bool canMove(int x, int y, int type) {
    for (int i = 0; i < 3; i++) {
        if (!check[type][i]) continue;
 
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (!isInner(nx, ny) || map[nx][ny] == 1) return false;
    }
    return true;
}
 
int movePipe(int x, int y, int type) {
 
    if (x == N - 1 && y == N - 1) return 1;
 
    int& ret = cache[x][y][type];
    if (ret != -1) return ret;
 
    ret = 0;
    for (int i = 0; i < 3; i++) {
        if (connect[type][i] && canMove(x, y, i)) {
            ret += movePipe(x + dx[i], y + dy[i], i);
        }
    }
    return ret;
}
 
void solution() {
    answer = movePipe(0, 1, 0);
}
 
int main() {
    //초기화
    N = 0;
    memset(map, 0, sizeof(map));
    memset(cache, -1, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

백트래킹과 DP에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17136 - 색종이 붙이기  (0) 2022.12.22
[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 16637 - 괄호 추가하기  (0) 2022.12.21
[C++] 백준 13460 - 구슬 탈출2  (1) 2022.12.21
[C++] 백준 2011 - 암호코드  (0) 2021.02.06

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

 

16637번: 괄호 추가하기

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

www.acmicpc.net

<풀이>

1. 수식을 입력받는다.

2. 괄호를 적절히 추가해서 얻을 수 있는 결과의 최대값을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우의 수를 다 해보아야 합니다. 따라서, 저는 브루트포스를 선택하였습니다.

 

2. 괄호 추가하기

=> 모든 숫자에서 괄호를 추가하는 경우와 안하는 경우로 나누어집니다. 3 + 8 * 7 - 9 * 2 를 예시로 들어보겠습니다. 8에서 괄호를 추가 안하는 경우는 전 숫자에 +8을 하고 다음 숫자 7로 넘어갑니다. 괄호를 추가하는 경우는 전 숫자에 +(8*7)을 하고 다음 숫자 9로 넘어갑니다. 위 방식이 반복적으로 일어나므로, 저는 재귀함수를 이용하여 구현하였습니다. 

 

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
#include <iostream>
#include <string.h>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
int N;
int nCnt, oCnt;
int num[11];
char oper[10];
int answer;
 
int calculate(int n1, int n2, char oper) {
    switch (oper) {
    case '+':
        return n1 + n2;
    case '-':
        return n1 - n2;
    case '*':
        return n1 * n2;
    }
}
 
int findMaxValue(int idx, int sum) {
 
    if (idx >= nCnt) {
        return sum;
    }
 
    int ret = INT_MIN;
    int nSum = 0;
 
    //괄호 X
    nSum = calculate(sum, num[idx], oper[idx - 1]);
    ret = max(ret, findMaxValue(idx + 1, nSum));
    //괄호 O
    if (idx + 1 < nCnt) {
        nSum = calculate(sum, calculate(num[idx], num[idx + 1], oper[idx]), oper[idx - 1]);
        ret = max(ret, findMaxValue(idx + 2, nSum));
    }
 
    return ret;
}
 
void solution() {
    answer = findMaxValue(1, 0);
}
 
int main() {
    //초기화
    N = 0;
    nCnt = 1, oCnt = 1;
    memset(num, 0, sizeof(num));
    memset(oper, '+', sizeof(oper)); //시작할때 '0 +'로 시작하기 위해
    answer = 0;
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        char c;
        cin >> c;
        if (i % 2 == 0) num[nCnt++] = c - '0';
        else oper[oCnt++] = c;
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17135 - 캐슬 디펜스  (0) 2022.12.21
[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21
[C++] 백준 13460 - 구슬 탈출2  (1) 2022.12.21
[C++] 백준 2011 - 암호코드  (0) 2021.02.06
[C++] 백준 2156 - 포도주 시식  (0) 2021.01.25

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

<풀이>

1. 보드 상태를 입력받는다.

2. 빨간 구슬을 뺄 수 있는 최소 움직임을 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 모든 경우를 다 해보지 않고서는 풀 수 없습니다. 저는 문제를 읽고 모든 경우를 다 해보는 브루트포스를 선택하였습니다.

 

2. 중복된 탐색 줄이기

=> 모든 경우를 다 해볼경우 중복된 경우가 많이 나올 수 있습니다. 예를 들어, 오른쪽 왼쪽을 반복하는 경우가 있습니다. 저는 중복된 경우를 줄이기 위해서, 빨간공과 파란공의 좌표의 조합으로 방문배열(visited[redX][redY][blueX][blueY])을 반들었습니다. 이렇게 하면 전에 탐색했던 빨간공과 파란공 좌표는 탐색하지 않으므로 중복을 줄일 수 있습니다.

 

3. 구슬 굴리는 방법

=> 각자 구슬을 신경쓰지 않고 일단 굴립니다. 이 때 겹쳐질 수도 있습니다. 이 후 두 구슬이 같은 곳에 있다면, 움직인 거리에 따라서 구슬의 위치를 정렬합니다. 

 

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, M;
char map[10][10];
bool visited[10][10][10][10];
int rX, rY, bX, bY;
int answer;
 
bool isExit(int x, int y) {
    if (map[x][y] == 'O') return true;
    return false;
}
 
bool isSamePosition(int x1, int y1, int x2, int y2) {
    if (x1 == x2 && y1 == y2) return true;
    return false;
}
 
void roll(int& x, int& y, int& dir, int& distance, bool& exit) {
    while (map[x+dx[dir]][y+dy[dir]] != '#') {
        x += dx[dir];
        y += dy[dir];
        distance++;
        if (map[x][y] == 'O') {
            exit = true;
            break;
        }
    }
}
 
int simulation(int rx, int ry, int bx, int by, int cnt) {
 
    if (cnt > 10) return INF;
 
    if (isExit(rx, ry) || isExit(bx, by)) {
        if (isExit(bx, by)) return INF;
        return 0;
    }
 
    int ret = INF;
 
    for (int i = 0; i < 4; i++) {
        int nrx = rx, nry = ry, nbx = bx, nby = by;
        int rd = 0, bd = 0;
        bool re = false, be = false;
 
        roll(nrx, nry, i, rd, re);
        roll(nbx, nby, i, bd, be);
 
        //둘 중 하나라도 탈출한 경우
        if (re || be) {
            ret = min(ret, simulation(nrx, nry, nbx, nby, cnt + 1) + 1);
        }
        else {
            //구슬 순서 정리
            if (isSamePosition(nrx, nry, nbx, nby)) {
                if (rd > bd) nrx -= dx[i], nry -= dy[i];
                else nbx -= dx[i], nby -= dy[i];
            }
 
            if (!visited[nrx][nry][nbx][nby]) {
                visited[nrx][nry][nbx][nby] = true;
                ret = min(ret, simulation(nrx, nry, nbx, nby, cnt + 1) + 1);
                visited[nrx][nry][nbx][nby] = false;
            }
        }
    }
 
    return ret;
}
 
void solution() {
    visited[rX][rY][bX][bY] = true;
    answer = simulation(rX, rY, bX, bY, 0);
    visited[rX][rY][bX][bY] = false;
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 0, M = 0;
    memset(map, '0', sizeof(map));
    memset(visited, false, sizeof(visited));
    rX = 0, rY = 0, bX = 0, bY = 0;
    answer = 0;
 
    //입력
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                map[i][j] = '.';
                rX = i, rY = j;
            }
            else if (map[i][j] == 'B') {
                map[i][j] = '.';
                bX = i, bY = j;
            }
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS와 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 17070 - 파이프 옮기기1  (1) 2022.12.21
[C++] 백준 16637 - 괄호 추가하기  (0) 2022.12.21
[C++] 백준 2011 - 암호코드  (0) 2021.02.06
[C++] 백준 2156 - 포도주 시식  (0) 2021.01.25
[C++] 백준 1074 - Z  (0) 2021.01.18

+ Recent posts

티스토리툴바