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

 

17471번: 게리맨더링

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

www.acmicpc.net

 

먼저 그래프가 연결된 정점 정보로 주어지므로 vector 배열을 사용해서 인접 리스트를 구현해주었다.

adjlist[x] 에는 x에 연결된 정점들을 push해준다.

 

 

 

인구 차이가 가장 적게 나도록 선거구를 나누기 위해서는

DFS로 각 구역들을 선거구 1에 넣는 경우와 선거구 2에 넣는 경우를 모두 구해서 계산해본다.

선거구에 넣을 때, 나중에 BFS탐색 시 연결되어 있는지 확인하기 위해서 check배열을 추가적으로 사용하였다.

선거구 1에 넣는 경우는 check배열의 값을 true로 선거구 2에 넣는 경우는 check배열의 값을 false로 하였다.

 

 

 

각각의 경우에서 BFS탐색으로 한 선거구에 포함되어 있는 구역이 모두 연결되어 있는지 검사해줘야 하는데, 선거구 1과 선거구 2를 각각 BFS로 검사해줬다.

 

 

 

먼저 선거구 1을 검사할 때는 선거구에 있는 지역 하나를 처음에 큐에 넣고 연결된 구역들을 방문하며 방문 체크를 한다.

이때, check배열의 값이 false인 경우(선거구 2인 경우) 방문하지 못한다. BFS탐색이 끝난 후에 같은 선거구인데 방문하지 않았다면 한 선거구 내에 연결되지 않은 구역이 있다는 뜻이므로 false를 리턴한다.

 

 

 

마찬가지로 선거구 2를 검사할 때에도 check배열의 값이 true인 경우 (선거구 1인 경우)를 방문하지 않고 연결된 정점들을 모두 방문한다. 그리고 선거구 내에 방문하지 않은 구역이 있다면 false를 리턴한다.

 

 

 

 

위의 두 가지 경우에서 모두 false를 리턴하지 않았다면 두 선거구가 모두 각 선거구 내의 구역들이 연결되어 있다는 뜻이므로 true를 리턴하고 인구 차이를 계산한다.

 

 

 

 

/*구역의 수가 최대 10개이고, 각 구역의 인구수가 최대 100명이므로 두 구역의 인구 차이가 최대 1000명을 넘지 않으므로 정답을 저장할 ans변수의 초기값을 1000으로 해두었다 */

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n;
int ans;
 
//인구 수 저장
int arr[11];
 
//인접리스트
vector<int> adjlist[11];
 
//선거구 1
vector<int> vt1;
 
//선거구 2
vector<int> vt2;
 
//선거구 1인 경우 true, 선거구 2인 경우 false
bool check[11];
 
//BFS할때 방문체크 배열
bool visit[11];
 
 
bool bfs() {
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
 
    //선거구 1이 모두 연결되어 있는지 검사
    queue<int> q;
    q.push(vt1[0]);
    visit[vt1[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        //현재 구역과 연결된 구역들을 검사한다
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            //이미 방문한 경우
            if (visit[nx]) continue;
            //선거구 2인 경우
            if (!check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 1에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt1) {
        if (!visit[x]) return false;
    }
 
 
    //방문배열 초기화
    for (int i = 0; i <= n; i++) visit[i] = false;
    
    //선거구 2가 연결되어 있는지 검사
    q.push(vt2[0]);
    visit[vt2[0]] = true;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        int size = adjlist[x].size();
        for (int k = 0; k < size; k++) {
            int nx = adjlist[x][k];
            if (visit[nx]) continue;
            //선거구 1인경우
            if (check[nx]) continue;
 
            visit[nx] = true;
            q.push(nx);
        }
    }
 
    //선거구 2에 연결되지 않은 구역(방문하지 못한 구역)이 있다면 false를 리턴
    for (int x : vt2) {
        if (!visit[x]) return false;
    }
 
    //각 선거구가 모두 연결되어 있다면 true를 리턴 
    return true;
}
 
 
void calc() {
    if (bfs()) {//각 선거구가 모두 연결되어 있다면 인구차이를 계산
        int sum = 0;
 
        //선거구 1과 선거구 2의 인구차이를 구한다.
        for (int x : vt1) sum += arr[x];
        for (int x : vt2) sum -= arr[x];
        if (sum < 0) sum = -sum;
 
        //최솟값보다 적다면 최솟값 갱신
        if (ans > sum) ans = sum;
    }
 
 
}
 
 
void solve(int index) {
    if (index > n) {
        //선거구에는 최소 1개의 구역이 포함되어야 한다
        if (vt1.size() == 0 || vt2.size() == 0) return;
        
        //인구차이를 계산
        calc();
        return;
    }
 
    //index구역을 선거구 1에 넣는 경우
    vt1.push_back(index);
    check[index] = true;
    solve(index + 1);
    check[index] = false;
    vt1.pop_back();
 
    //index구역을 선거구 1에 넣는 경우
    vt2.push_back(index);
    solve(index + 1);
    vt2.pop_back();
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    int cnt, x;
    for (int i = 1; i <= n; i++) {
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            cin >> x;
            adjlist[i].push_back(x);
        }
        
    }
 
    ans = 1000;
 
    solve(1);
 
    //ans값이 갱신되지 않았다면 두 선거구로 나눌수없는 경우이다.
    if(ans != 1000) cout << ans << '\n';
    else cout << -1 << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17472. 다리 만들기 2  (0) 2019.10.16
[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02

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

 

17141번: 연구소 2

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로

www.acmicpc.net

처음에 입력을 받을 때 바이러스를 놓을 수 있는 칸(값이 2인 칸)을 벡터에 모두 넣어놓는다.

그리고 이 칸들 중 m개를 선택하여 바이러스 퍼트리는 경우를 모두 해보고 최소 시간을 구한다.

 

 

m개를 모두 골라줬다면 골라준 자리에 바이러스를 넣고 퍼뜨린다.

바이러스를 퍼트리기 위해서 bfs를 사용하고 시간을 구하기 위해서 큐 사이즈만큼 단계별로 진행하였다.

그리고 각 큐 사이즈만큼 시작할 때마다 시간을 1씩 증가시켜서 시간을 구할 수 있다.

이렇게 하면 나중에 큐가 비었을 때도 한 번 더 1이 더해지므로 처음에 시간을 -1부터 시작하든지 나중에 1을 빼주던지 하면 된다.

 

 

바이러스를 모두 퍼뜨렸다면 퍼지는데 걸리는 시간을 리턴해주면 되는데,

모든 빈칸에 바이러스를 퍼졌는지 먼저 검사해주어야 한다.

빈칸인데 바이러스가 퍼져있지 않다면 문제 조건에 따라 시간 대신에 -1을 리턴한다.

 

 

그리고 시간의 최솟값을 구하기 위해서 먼저 정답을 저장할 ans에다가 -1을 초기값으로 넣어놓고 ans가 -1인 경우와 -1이 아닌경우를 나눠서 최솟값을 구해줬다.

먼저 -1인 경우에는 ans가 초기값이거나 bfs의 결괏값이 -1인 경우이다. 이때는 그냥 새로 bfs 한 결과를 바로 넣어주면 된다. -1이 아닌 경우에는 bfs의 결과가 -1이 아닌 ans보다 작은 값이 어야 ans값으로 새로 갱신된다.

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
int ans;
int map[50][50];
bool check[50][50];
vector<pair<int,int> > vt;
vector<int> virus;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int bfs() {
    queue<pair<int, int> > q;
    memset(check, false, sizeof(check));
 
    int x, y;
    //선택한 바이러스를 놓을 수 있는 칸에 바이러스를 놓는다.
    for (int i = 0; i < m; i++) {
        x = vt[virus[i]].first;
        y = vt[virus[i]].second;
 
        q.push(make_pair(x,y));
        check[x][y] = true;
    }
 
 
    int time = -1;
    while (!q.empty()) {
 
        int size = q.size();
        time++;
 
        while (size--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
 
                //범위
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                //방문체크
                if (check[nx][ny]) continue;
                //벽인경우
                if (map[nx][ny] == 1) continue;
 
                q.push(make_pair(nx, ny));
                check[nx][ny] = true;
 
            }
        }
        
    }
 
    //바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            //빈칸인데 바이러스가 퍼져있지 않다
            if (map[i][j] == 0 && !check[i][j]) return -1;
        }
    }
 
    return time;
 
}
 
void select(int index, int cnt) {
    if (cnt == m) {
        int tmp = bfs();
        if (ans == -1) ans = tmp;
        else {
            if (tmp != -1 && ans > tmp) ans = tmp;
        }
 
        return;
    }
    if (index == vt.size()) {
        return;
    }
 
 
    //index번째 바이러스를 놓는 경우
    virus.push_back(index);
    select(index + 1, cnt+1);
    virus.pop_back();
 
    //바이러스를 놓지 않는 경우
    select(index + 1, cnt);
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
            //바이러스를 놓을 수 있는 칸이면 벡터에 넣는다.
            if (map[i][j] == 2) vt.push_back(make_pair(i, j));
        }
    }
 
    ans = -1;
 
    select(0, 0);
    
    cout << ans << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2146. 다리 만들기  (0) 2019.10.16
[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 2217. 로프  (0) 2019.09.02

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

 

6359번: 만취한 상범

문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고

www.acmicpc.net

먼저 상범이는 첫 번째 라운드에서 모든 방의 문을 열고, 그다음 라운드부터는 

k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다.

이런 식으로 n번째 라운드까지 진행한다.

 

문제의 입력으로 테스트 케이스와 함께 n값이 주어진다. n값은 방의 개수이자 라운드 진행 수이다.

 

이 문제는 2번째 라운드에서 2의 배수인 방들은 문이 잠겨져 있고 나머지 방들은 열려있는 상태에서

3번째 라운드를 진행한다.

즉, i번째 라운드의 상태에서 i+1번째 라운드의 상태로 바뀌므로 DP(Dynamic Programming)로 해결할 수 있다.

 

n(5 ≤ n ≤ 100)

n의 범위가 위와 같으므로 n이 100인 경우까지 모두 미리 구해놓으면 된다.

DP 식은 다음과 같이 정의할 수 있다.

 

dp[i][j] = true (i번째라운드의 j번 방이 열려있다)

dp[i][j] = false (i번째라운드의 j번 방이 잠겨져 있다)

 

위의 식을 이용하여 1번째라운드부터 n번째라운드까지 순차적으로 구할 수 있다.

dp배열을 모두 구해놨다면 n이 주어졌을 때, dp[n][i] (1<= i <= n) 중 true인 값들(열려있는 방)의 개수를 구해주면 된다.

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
#include<iostream>
#include <cstring>
using namespace std;
 
bool d[101][101];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    //열리면 true 잠기면 false
    //1번째 라운드에서 모든 방을 연다. (true로 초기화)
    memset(d[1], true, sizeof(d[1]));
    
 
 
    //i번째 라운드에서 j번 방 문을 열거나 잠근다.
    for (int i = 2; i <= 100; i++) {
 
        //이전 방 문의 상태를 복사
        for (int j = 1; j <= 100; j++) {
            d[i][j] = d[i - 1][j];
        }
 
        //i의 배수인 방 문만 열거나 잠근다.
        for (int j = i; j <= 100; j += i) {
            if (d[i - 1][j]) d[i][j] = false;
            else d[i][j] = true;
        }
    }
 
 
    int T;
    cin >> T;
 
    int n;
    while (T--) {
        cin >> n;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            //문이 열려있다
            if (d[n][i]) cnt++;
        }
 
        cout << cnt << '\n';
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17471. 게리맨더링  (0) 2019.10.16
[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 2217. 로프  (0) 2019.09.02
[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02

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

 

1931번: 회의실배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 회의 수를 찾으면 된다.

 

 

문제에서 주어진 예제만 봐도 회의 진행시간이 짧은 순서로 진행하면 안 된다는 것을 알 수 있다. 물론 시작하는 시간이 빠른 것도 안된다. 한참 헤매다가 끝나는 시간을 기준으로 하면 된다는 것을 깨달았다...

 

 

끝나는 시간을 오름차순으로 정렬하여서 먼저 끝나는 회의를 진행하고 그 회의 바로 다음에 할 수 있는 끝나는 시간이 가장 빠른 회의를 진행하면 된다.

 

 

나는 벡터에 시작시간과 끝나는 시간을 pair로 넣어서 정렬했다.

pair는 first값을 기준으로 먼저 정렬되고 그다음으로 second값을 기준으로 정렬되기 때문에 

끝나는 시간을 앞에 넣어주었다. 그러면 끝나는 시간이 빠른 순으로 정렬된다.

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
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    int s, e;
    vector<pair<int, int> > vt;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> s >> e;
        vt.push_back(make_pair(e, s));
    }
 
 
    sort(vt.begin(), vt.end());
 
 
    //끝나는 시간
    int now = vt[0].first;
    
    //회의 수
    int ans = 1;
 
    for (int i = 1; i < n; i++) {
        //현재 회의가 끝나는 시간 보다 빨리 시작하는 회의는 진행하지 못한다.
        if (vt[i].second < now) continue;
 
        //다음 회의가 끝나는 시간
        now = vt[i].first;
        ans++;
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17141. 연구소 2  (0) 2019.09.06
[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 2217. 로프  (0) 2019.09.02
[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02
[BOJ] 11729. 하노이 탑 이동 순서  (0) 2019.08.31

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

 

2217번: 로프

N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을

www.acmicpc.net

로프를 k개 (1 <= k <= n) 만큼 사용하는 경우 로프들을 이용해서 들 수 있는 중량을 모두 구해서 그중 최댓값이 최대 중량이 된다.

 

 

먼저 1개만 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프의 경우가 최댓값이다.

그리고 2개만 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프와 두번째로 큰 로프 두 개를 사용하여야 들 수 있는 최대 중량을 만들 수 있을 것이다. 이런식으로 k개의 로프를 사용하는 경우에는 들 수 있는 중량이 가장 큰 로프 k개를 사용하는 것이 최댓값이므로 로프를 내림차순으로 정렬해준다.

 

 

그리고 문제에서

 k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

라고 하였으므로 k개를 사용할 때는 (가장 작은 로프의 값 X k) 만큼이 들어올릴 수 있는 중량이다.

이렇게 k개를 사용하는 모든 경우의 중량 중 최대 중량이 정답이다.

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>
using namespace std;
 
int arr[100000];
 
bool comp(int a, int b) {
    //내림차순
    return a > b;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
    //내림차순 정렬
    sort(arr, arr + n, comp);
 
    //처음에 가장 큰 값(0번째 값)을 저장
    int ans = arr[0];
 
    for (int i = 1; i < n; i++) {
        if (ans < (arr[i] * (i + 1))) {
            ans = (arr[i] * (i + 1));
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 6359. 만취한 상범  (0) 2019.09.04
[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02
[BOJ] 11729. 하노이 탑 이동 순서  (0) 2019.08.31
[BOJ] 별 찍기 - 10  (0) 2019.08.31

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

www.acmicpc.net

부호는 +와 -만 있고 값을 최소로 만들면 되므로 - 이후의 값들은 모두 괄호로 적절히 묶어서 -로 만들어 주면 된다. 

 

예를 들어 문제에 나온 예시인 55-50+40의 경우 55-(50+40) 이런 식으로 만들어줄 수 있다.

55-50+40-10 인 경우에는 55-(50+40)-10 이런 식으로 묶어준다고 생각하면 되므로 그냥 - 이후의 값들은 모두 음수 값으로 처리해준다.

 

음수 값으로 바꾸기 위해서 나는 flag라는 변수에 처음에 1을 넣어놓고 -가 나오기 전까지는 숫자가 들어올 때마다 flag를 곱해줬다. 그리고 - 부호가 들어오면 flag를 -1로 만들어서 더해지는 숫자가 마이너스 값이 되도록 했다.

 

 

 

구체적으로는 입력으로 들어오는 문자열의 각 문자에 대해서

+인 경우 / -인 경우 / 그 외의 경우(숫자)로 나눠서 각각 처리해주었다.

 

먼저 숫자인 경우에는 num 변수에 숫자를 저장해놨다가 +나 -가 나와서 숫자가 끝나면 num을 최종 값인 ans 변수에 더해주었다. 숫자가 연속으로 나올 수 있기 때문에 이전에 저장된 수에 10을 곱해준 후에 현재 문자를 숫자로 바꿔서 더해준다.

 

 55-50+40

문제의 예시를 다시 보면

5가 나오면 먼저 num에 5가 저장된다. 처음에 num에는 0이 저장되어 있으므로 10을 곱해주는 것은 상관없다.

그다음에 또 5가 들어오면 기존에 있던 5에 10을 곱해줘서 50으로 만들어주고 새로 들어온 5를 곱해준다.

그리고 -가 나오면 num에 있는 55를 ans에 더해준다. 뒤의 50과 40도 같은 방법으로 만들 수 있다.

 

 

+인 경우는 그냥 이전까지의 숫자(num)를 ans에 더해주고 num을 초기화해주면 된다.

 

-인 경우에는 위의 설명처럼 flag를 -1로 바꿔준다. 그리고 +와 마찬가지로 앞에서 숫자가 끝났으므로, 최종 값(ans)에 이전까지의 숫자(num)를 더해준다. 

 

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
#include<iostream>
#include <string>
using namespace std;
 
int arr[1000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string s;
    cin >> s;
 
    int num = 0;
    int ans = 0;
    int flag = 1;
 
    for (char c : s) {
        if (c == '+') {
            //+가 나온 경우 숫자가 끝난 것이므로 num을 ans에 더해준 후 에 num을 0으로 초기화
            ans += num;
            num = 0;
        }
        else if (c == '-') {
            //- 인 경우 flag를 -1로 바꿔주고 이전까지의 num을 ans에 더해준다.
            //flag는 이후로 계속 -1 을 유지한다.
            flag = -1;
            ans += num;
 
            //더해줬으므로 num은 다시 0으로 초기화
            num = 0;
        }
        else {
            //숫자인 경우 num에 저장
            num = num * 10 + (c - '0')*flag;
        }
    }
 
    //마지막 숫자를 더해준다.
    ans += num;
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1931. 회의실배정  (0) 2019.09.02
[BOJ] 2217. 로프  (0) 2019.09.02
[BOJ] 11729. 하노이 탑 이동 순서  (0) 2019.08.31
[BOJ] 별 찍기 - 10  (0) 2019.08.31
[BOJ] 1655. 가운데를 말해요  (2) 2019.08.30

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

 

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5

www.acmicpc.net

하노이 탑 문제는 재귀 호출을 이용하여 풀 수 있는 대표적인 문제이다.

먼저 옮기는 횟수는 원판의 개수가 n 개라고 했을 때 2의n제곱-1 이므로 먼저 출력해주고 시작할 수 있다.

 

 

장대 세개가 각각 a, b, c  (각각 1, 2, 3)라고 했을 때, n개의 원판을 a에서 c로 옮기려고 한다.

규칙에 따라서 맨 밑에 있는 원판이 c에 가장 먼저 놓여야 하는데, 그러기 위해서는 맨 밑 원판을 제외한 나머지 n-1개의 원판을 다른 비어있는 장대(b)로 옮겨놓아야 한다. 그리고 맨 밑 원판을 c로 옮겼으면 아까 옮겨 놓았던 n-1개의 원판을 다시 c로 가져온다.

 

 

이 때, a에서 b로 옮겨진 n-1개의 원판들도 같은 규칙으로 옮길 것이기 때문에 위의 내용을 그대로 재귀 함수로 구현해주면 된다.

즉, n-1개의 원판을 a에서 b로 옮기려고 하는 경우에 대해서 새로 구해주는 것이다.

 

 

a는 1, b는 2라고 했을 때, c는 6 - a - b로 표현할 수 있다.

a + b + c = 6

(1 + 2 + 3) = 6

 

 

밑의 코드에서는 처음 넘겨지는 a는 1, b는 3이다. (첫 번째 장대에서 세 번째 장대로 옮길 것이므로)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
 
 
void hanoi(int n, int a, int b) {
    if (n == 0) return;
    
    hanoi(n - 1, a, 6 - a - b);
    printf("%d %d\n", a, b);
    hanoi(n - 1, 6 - a - b, b);
 
}
 
int main() {
    int n;
    cin >> n;
 
    cout << (1 << n) - 1 << '\n';
 
    hanoi(n, 1, 3);
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2217. 로프  (0) 2019.09.02
[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02
[BOJ] 별 찍기 - 10  (0) 2019.08.31
[BOJ] 1655. 가운데를 말해요  (2) 2019.08.30
[BOJ] 17143. 낚시왕  (0) 2019.08.18

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

 

2447번: 별 찍기 - 10

첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8)

www.acmicpc.net

문제에는 아래 그림과 같은 출력 결과를 주고 규칙을 찾아서 별을 찍으라고 나와있다. N은 항상 3의 제곱 꼴인 수라는 게 힌트다.

아래 그림은 N이 27인 경우인데 27인 경우 27*27 모양이고 빈칸이 비어 있는 모양인 것을 볼 수 있다.

 

 

N이 9였다면 아래 그림과 같이 9*9 크기의 빨간 네모 부분이 출력됐을 거다. 여기서도 마찬가지로 가운데 부분이 비어있다는 것을 알 수 있다. N이 3인 경우에도 왼쪽 맨 위쪽 끝부터 3*3크기를 보면 가운데 비어있는 모양인 것을 볼 수 있다.

결국 이 문제는 처음에 27을 입력받았다면 3으로 나눠서 각각 9*9로 이루어진 9칸을 다시 9칸을 모두 각각 3으로 나눠서 3*3인 칸에 대해서 별을 찍으면 된다. 즉 재귀를 이용하여 분할 정복(Divide and Conquer)으로 풀 수 있다.

 

 

n이 1이 될때까지 계속 3으로 나눠서 재귀 호출을 한다. 호출에서 재귀 호출은 총 8번 일어난다.

가운데 빈칸을 제외하고 총 위쪽 3개, 아래쪽 3개, 가운데 2개를 별을 찍어줘야하기 때문이다.

별은 n이 1이 될때까지 분할한 후에 찍어준다.

 

 

예를 들어 n이 9인 경우 아래 그림에서 빨간 네모 부분과 같은 3*3 만큼씩 각각 8번 호출하게 된다. (가운데 부분은 호출하지 않기 때문)

처음에 (0,0)에서 시작했다면 그다음은 (0,3)에서 시작하고 그다음은 (0,6)에서 호출한다.

다시 그다음은 중간 시작점인 (3,0)이고 그다음 (3,3)은 가운데 이므로 호출하지 않고 넘어간다. 이런 식으로 재귀 호출을 진행하면

각 호출에서는 다시 3*3 에 대해서 다시 8번 호출을 하여 1*1이 되어서 별을 찍게 된다.

 

 

 

(배열의 크기는 문제에서 주어진 최대 값이 3의 8 제곱보다 큰 수 2200으로 잡았다)

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
#include <iostream>
using namespace std;
 
char map[2200][2200];
 
void solve(int x, int y, int n) {
 
    if (n == 1) {
        map[x][y] = '*';
        return;
    }
 
    int div = n / 3;
    
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            //가운데인 경우 별을 찍지 않는다.
            if (i == 1 && j == 1) continue;
 
            solve(x+ (div * i), y+(div * j), div);
        }
    }
 
}
 
int main() {
 
    int n;
    cin >> n;
 
 
    //먼저 공백으로 채워준다.
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = ' ';
        }
    }
 
    
    solve(0, 0, n);
 
 
    //출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << map[i][j];
        }
        cout << '\n';
    }
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1541. 잃어버린 괄호  (0) 2019.09.02
[BOJ] 11729. 하노이 탑 이동 순서  (0) 2019.08.31
[BOJ] 1655. 가운데를 말해요  (2) 2019.08.30
[BOJ] 17143. 낚시왕  (0) 2019.08.18
[BOJ] 17406. 배열 돌리기 4  (0) 2019.08.13

+ Recent posts

티스토리툴바