반응형

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

 

17837번: 새로운 게임 2

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하

www.acmicpc.net

https://youtu.be/fAs85oVcu1g

접근법은 위 동영상과 동일하다.

말의 위치를 나타내는 node_map[][]과

말의 정보를 나타내는 node_arr[]를 사용했다.

하지만 구현을 잘 못해서 그런지, 4%에서 틀렸습니다가 계속 떴다

테스트 케이스 5개는 모두 맞게 나오고 질문 게시판도 다 읽어봤는데 원인을 못 찾았다...

 

5번 테스트 케이스의 진행과정

01234567

진행과정은 백준 게시판에 있는 설명과 동일하다

https://www.acmicpc.net/board/view/49492

 

글 읽기 - test 케이스별 참고자료

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

질문 게시판에서 4%에서 틀렸습니다가 뜬다는 글을 읽어보면 배열 범위 문제인 것 같은데,

배열 범위도 넉넉하게 잡았고, 범위 체크도 다 한 것 같은데...

 

파란색 혹은 벽을 만났을 때 반대 방향으로 이동 시, 반대 방향의 색 (흰 / 빨강 / 파랑)도 체크했고,

빨간색 칸에 기존 말이 존재할 경우, 기존 말의 순서는 바뀌지 않고 새로 이동한 말의 순서만 뒤집는 것도 체크했다.

 

소스코드 (4%에서 틀렸습니다.)

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 <vector>
#include <stack>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
struct Node {
    int i, j, d, idx;
};
int dx[] = { -1, 0, 0, -1, 1 };
int dy[] = { -1, 1, -1, 0, 0 };
int n, k;
int arr[13][13];
vector<int> node_map[13][13];
Node node_arr[11];
stack<int> s;
void input();
void changeDirection(Node &now) {
    if (now.d == 1) now.d = 2;
    else if (now.d == 2) now.d = 1;
    else if (now.d == 3) now.d = 4;
    else if (now.d == 4) now.d = 3;
}
int func() {
    int cnt = 1;
    while (cnt <= 1000) {
        rep(i, k) {
            // 지금 이동시킬 말이 몇 번째 칸에서 몇 번째 순서인지 확인하기
            Node start = node_arr[i];
            int x = start.i;
            int y = start.j;
 
            // 현재 말 위에 쌓여있는 것들은 현재 말의 방향 따라 움직임
            int nx = x + dx[start.d];
            int ny = y + dy[start.d];
 
            bool added = true;
            // 현재 말의 위치에서 현재 말보다 뒤에 (위에) 있는 것들은 다 같이 이동시키기
        
            for (int idx = start.idx; idx < node_map[x][y].size(); idx++) {
                int node_num = node_map[x][y][idx];
                Node &now = node_arr[node_num];
 
                // 다음 칸이 벽 또는 파란색
                if (nx<1 || nx>n || ny<1 || ny>n || arr[nx][ny] == 2) {
                    changeDirection(now);
                    
                    nx = now.i + dx[now.d];
                    ny = now.j + dy[now.d];
                    
                    // 이동할 칸이 파란색이면 정지
                    if (nx<1 || nx>n || ny<1 || ny>n || arr[nx][ny] == 2) {
                        added = false;
                        break;
                    }
                }
                // 위치 이동
                now.i = nx;
                now.j = ny;
                
                // 다음 칸이 흰 색
                if (arr[nx][ny] == 0) {
                    now.idx = node_map[nx][ny].size();
                    node_map[nx][ny].push_back(node_num);
                }
 
                // 다음 칸이 빨간 색
                else if (arr[nx][ny] == 1) {
                    // 순서 뒤집어야함
                    s.push(node_num);
                }
 
                // 이동시킨 칸에 말이 4개 쌓이면 즉시 종료
                if (node_map[nx][ny].size() >= 4)
                    return cnt;
            }
 
            // 빨간색일 경우 처리
            while (!s.empty()) {
                int now = s.top(); s.pop();
                node_arr[now].idx = node_map[nx][ny].size();
                node_map[nx][ny].push_back(now);
            }
 
            // 기존 칸에서 지우기
            while (added&&node_map[x][y].size() > start.idx)
                node_map[x][y].erase(node_map[x][y].begin() + start.idx);
        }
        cnt++;
    }
    return cnt;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    int ret = func();
    cout << (ret > 1000 ? -1 : ret);
}
void input() {
    cin >> n >> k;
    rep(i, n) {
        rep(j, n)
            cin >> arr[i][j];
    }
    rep(i, k) {
        Node node;
        cin >> node.i >> node.j >> node.d;
        node.idx = 0;
        node_arr[i] = node;
        node_map[node.i][node.j].push_back(i);
    }
}
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17779 [복습 필수]  (0) 2021.08.06
백준 17142  (0) 2021.08.04
백준 17143  (0) 2021.07.19
백준 5373 [복습필수]  (0) 2021.04.30
백준 16234  (0) 2021.04.30
반응형

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

 

17779번: 게리맨더링 2

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름

www.acmicpc.net

처음 접근법

: 5구역을 먼저 계산하고 1~4구역을 계산

 

① 5구역 계산하면서 visited 체크

② 1~4구역을 문제에서 주어진 수식대로 범위를 지정하여 계산.

    for문을 돌리면서 visited 처리가 된 것은 5구역에 포함되는 부분이므로, 각 구역 계산 시 포함시키지 않음

 

문제점

1~4구역 나누는 것은 문제에 주어진 수식을 참고하여 코드를 작성했지만,

5구역 나누는 법은 도무지 생각이 나지 않았다...

 

두 번째 접근법 (블로그 참고)

: 1~4구역을 먼저 계산하고 5구역을 계산

 

① 1~4구역 계산 시, if 문에서 5구역을 걸러내는 조건을 이용해서 5구역 필터링.

② 전체 영억 - (1~4구역) 으로 5구역 계산

 

문제점

5구역을 걸러내는 조건이 아주 까다로웠다...

그림을 그려봐도, 코드를 계속 읽어봐도 이해가 안됐다.

무엇보다 비슷한 유형의 문제를 풀 때, 이 방법대로 구현할 자신이 없었다.

 

세 번째 접근법 (유튜브 참고): https://youtu.be/fAs85oVcu1g

 

 

: 5구역의 경계를 설정하고, 1~4구역 계산 시 필터링

 

 

① 문제에서 주어진 5구역 경계 수식을 참고하여 5구역 경계 설정

② 1~4구역 계산 시 5구역의 경계를 만나면 다음 행으로 넘어감

 

해결

이 영상 보자마자 바로 방법을 깨달았다.

단순하게 5구역의 경계만 설정함으로써 간단하게 1~4구역을 계산할 수 있었다.

복잡하게 5구역을 먼저 계산할 필요도, 1~4구역 계산 시 5구역 필터링을 어렵게 할 필요도 없는 것이다.

5구역의 경계를 설정하는 수식은 아주 간단하다. 문제에 있는 조건을 그대로 이용하면 된다.

 

문제에서 주어진 5구역의 경계

5구역의 경계를 표시하는 소스코드

1
2
3
4
5
6
7
8
9
    // 5구역 경계 설정
    for (int i = 0; i <= d1; i++) {
        border[x + i][y - i] = 5;             // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        border[x + d2 + i][y + d2 - i] = 5;   // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    }
    for (int i = 0; i <= d2; i++) {
        border[x + i][y + i] = 5;             // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        border[x + d1 + i][y - d1 + i] = 5;  // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    }
 cs

 

1~4구역 계산도 마찬가지로 문제에 주어진 수식을 활용하여 쉽게 수행할 수 있다.

 

문제에서 주어진 1~4구역의 범위

1~4구역 계산하는 소스코드

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
    // 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    for (int i = 1; i < x+d1; i++) {
        for (int j = 1; j <= y; j++) {
            if (border[i][j] == 5) break;
            area[1] += arr[i][j];
        }
    }
    // 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
    for (int i = 1; i <= x + d2; i++) {
        for (int j = n; j > y; j--) {
            if (border[i][j] == 5) break;
            area[2] += arr[i][j];
        }
    }
    // 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
    for (int i = x+d1; i <= n; i++) {
        for (int j = 1; j < y-d1+d2; j++) {
            if (border[i][j] == 5) break;
            area[3] += arr[i][j];
        }
    }
    // 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
    for (int i = x + d2+1; i <= n; i++) {
        for (int j = n; j >= y-d1+d2; j--) {
            if (border[i][j] == 5) break;
            area[4] += arr[i][j];
        }
    }
    // 5번 선거구
    area[5] = total;
    rep(i, 4)
        area[5] -= area[i];
 cs

 

진행 과정

0123

전체 소스코드

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, arr[21][21], area[6], border[21][21];
int max_val, min_val, ans = 1e9, total;
void input();
void init();
bool isValidArea(int x, int y, int d1, int d2);    // 범위 검사
void getArea(int x, int y, int d1, int d2);        // 범위 계산
 
// 1. (x, y), d1, d2 정하기
// 2. 구역 별 인구수 계산
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
 
    for (int x = 1; x <= n;x++) {
        for (int y = 1; y <= n;y++) {
            for (int d1 = 1; d1 < n; d1++) {
                for (int d2 = 1;d2 < n;d2++) {
                    init();
                    if (isValidArea(x, y, d1, d2)) {
                        getArea(x, y, d1, d2);
                        ans = min(ans, max_val - min_val);
                    }
                }
            }
        }
    }
    cout << ans;
}
bool isValidArea(int x, int y, int d1, int d2) {
    if (x<1 || x>n || y<1 || y>n) return 0;    //    상: (x,y)
    if (x + d1 + d2<1 || x + d1 + d2>n || y - d1 + d2<1 || y - d1 + d2>n) return 0;    //    하: (x+d1+d2, y-d1+d2)
    if (x + d1<1 || x + d1>n || y - d1<1 || y - d1>n) return 0;    //    좌: (x+d1, y-d1)
    if (x + d2<1 || x + d2>n || y + d2<1 || y + d2>n) return 0;    //    우: (x+d2, y+d2)
    return 1;
}
// 범위 계산
void getArea(int x, int y, int d1, int d2) {
    // 5구역 경계 설정
    for (int i = 0; i <= d1; i++) {
        border[x + i][y - i] = 5;            // 5-1 경계 (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        border[x + d2 + i][y + d2 - i] = 5;    // 5-4 경계 (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    }
    for (int i = 0; i <= d2; i++) {
        border[x + i][y + i] = 5;            // 5-2 경계 (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        border[x + d1 + i][y - d1 + i] = 5; // 5-3 경계 (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    }
 
    // 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
    for (int i = 1; i < x+d1; i++) {
        for (int j = 1; j <= y; j++) {
            if (border[i][j] == 5) break;
            area[1] += arr[i][j];
        }
    }
    // 2번 선거구 : 1 ≤ r ≤ x + d2, y < c ≤ N
    for (int i = 1; i <= x + d2; i++) {
        for (int j = n; j > y; j--) {
            if (border[i][j] == 5) break;
            area[2] += arr[i][j];
        }
    }
    // 3번 선거구 : x + d1 ≤ r ≤ N, 1 ≤ c < y - d1 + d2
    for (int i = x+d1; i <= n; i++) {
        for (int j = 1; j < y-d1+d2; j++) {
            if (border[i][j] == 5) break;
            area[3] += arr[i][j];
        }
    }
    // 4번 선거구 : x + d2 < r ≤ N, y - d1 + d2 ≤ c ≤ N
    for (int i = x + d2+1; i <= n; i++) {
        for (int j = n; j >= y-d1+d2; j--) {
            if (border[i][j] == 5) break;
            area[4] += arr[i][j];
        }
    }
    // 5번 선거구
    area[5] = total;
    rep(i, 4)
        area[5] -= area[i];
 
    rep(i, 5) {
        max_val = max(max_val, area[i]);
        min_val = min(min_val, area[i]);
    }
}
 
void input() {
    cin >> n;
    rep(i, n) {
        rep(j, n) {
            cin >> arr[i][j];
            total += arr[i][j];
        }
    }
}
void init() {
    memset(area, 0, sizeof(area));
    memset(border, 0, sizeof(border));
    max_val = -1;
    min_val = 1e9;
}
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17837 [4%에서 틀렸습니다.]  (0) 2021.08.08
백준 17142  (0) 2021.08.04
백준 17143  (0) 2021.07.19
백준 5373 [복습필수]  (0) 2021.04.30
백준 16234  (0) 2021.04.30
반응형

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

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고

www.acmicpc.net

1. 백트래킹으로 활성화 할 바이러스 선택

  - 2차원 배열에서 백트래킹하면 시간초과

  - arr[i][j] = 2인 {i, j} 값을 벡터에 저장시킨 뒤, 해당 벡터에 대해서 백트래킹 수행

 

2. m개 활성시켰으면 BFS로 시간 계산

  - arr[i][j]에서 BFS 수행하면 입력이 변경되므로, 다음 백트래킹 수행 시 계산 잘못됨

  - arr[i][j]가 아니라 copy_arr[i][j]에서 BFS 수행

 

0: 빈 칸

1: 벽

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
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int, int>
using namespace std;
queue<pii> q;
vector<pii> virus;
int n, m, arr[51][51], copy_arr[51][51], zero_cnt, ans = 1e9;
bool visited[51][51];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
void input();
void bfsInit() {
    memset(visited, 0, sizeof(visited));
    while (!q.empty())
        q.pop();
    zero_cnt = 0;
    rep(i, n) {
        rep(j, n) {
            copy_arr[i][j] = arr[i][j];
            // 활성화된 바이러스를 queue에 삽입하고 방문처리
            if (copy_arr[i][j] == 3) {
                q.push({ i,j });
                visited[i][j] = 1;
            }
            // 빈 칸의 개수 체크
            else if (copy_arr[i][j] == 0) zero_cnt++;
        }
    }
}
// return 시간(초)
int bfs() {
    int cnt = 0;
    bfsInit();
    while (!q.empty()) {
        int size = q.size();
        // 빈 칸 없으면 종료
        if (zero_cnt == 0) break;
        while (size--) {
            pii now = q.front(); q.pop();
            int x = now.first;
            int y = now.second;
            visited[x][y] = 1;
            rep(i, 4) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
                // 1: 벽이라서 멈춤
                if (copy_arr[nx][ny] == 1) continue;
 
                // 0, 2: 활성화 상태(3)로 변경 후 전파시킴
                else if (copy_arr[nx][ny] == 0 || copy_arr[nx][ny]==2) {
                    if (copy_arr[nx][ny] == 0) zero_cnt--;
                    copy_arr[nx][ny] = 3;
                    visited[nx][ny] = 1;
                    q.push({ nx, ny });
                }
                
                // 3: 이미 visited라서 걸러질 것
            }
        }
        cnt++;
    }
    return cnt;
}
 
void backTrackking(int idx, int cnt) {
    // 바이러스를 m개 만큼 활성화 시켰으면 bfs 실행
    if (cnt == m) {
        int ret = bfs();
 
        // 빈 칸 개수가 0개일 때만 갱신
        if (zero_cnt == 0)
            ans = min(ans, ret);
        return;
    }
 
    // 백트래킹으로 활성화시킬 바이러스 찾기
    for (int i = idx; i < virus.size(); i++) {
        int x = virus[i].first;
        int y = virus[i].second;
        if (arr[x][y] == 2) {
            arr[x][y] = 3;
            backTrackking(i, cnt + 1);
            arr[x][y] = 2;
        }
    }
}
// 1. 활성화 시킬 바이러스 선택하기 (백트래킹)
// 2. 시간 얼마나 걸리는지 계산하기 (bfs)
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    backTrackking(0, 0);
    cout << (ans==1e9?-1:ans);
}
 
void input() {
    cin >> n >> m;
    rep(i, n) {
        rep(j, n) {
            cin >> arr[i][j];
            if (arr[i][j] == 2)
                virus.push_back({ i,j });
        }
    }
}
 cs

 

반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17837 [4%에서 틀렸습니다.]  (0) 2021.08.08
백준 17779 [복습 필수]  (0) 2021.08.06
백준 17143  (0) 2021.07.19
백준 5373 [복습필수]  (0) 2021.04.30
백준 16234  (0) 2021.04.30
반응형

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

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

슈도 코드

● 낚시왕이 오른쪽으로 한 칸 이동한다.

rep(pos, c) {

        ① 지면과 가장 가까운 상어 찾기

 

        ② 상어의 다음 위치 계산 (어려움)

            -> 큐에 상어의 다음 위치 삽입: q.push({ nr, nc, ... })          ------------------- ★

            -> 현재 위치에서 제거: arr[row][col] = {0, 0, 0, 0, 0}

 

        ③ 큐에 있는 상어를 하나씩 꺼내서 상어의 새 위치를 배열에 반영

            -> (현재 상어 크기) > (기존에 있는 상어 크기) ? 현재 상어 : 기존 상어

}

 

★ 큐에 상어의 다음 위치를 삽입하는 이유

상어의 다음 위치 계산 한 뒤에 (nr, nc) 상어를 바로 이동시키면 기존 (nr, nc) 위치에 있던 상어의 정보가 덮어씌워져서 계산을 할 수 없다. 이를 방지하기 위해 상어의 새 위치를 계산 즉시 반영시키지 않고 Queue에 저장해놨다가, 모든 상어의 새 위치가 계산된 후에 상어의 새 위치를 반영한다.

 

ex)

A 상어가 (4, 2) -> (4, 3)으로 이동하고, B 상어가 (4, 3)에 위치할 경우

A 상어를 (4, 3)으로 이동시키면 B 상어의 새 위치를 계산하지 못함

 

상어의 다음 위치 계산

C = 5

속도가 0일 때와 8일 때 방향, 위치 모두 동일한 것을 알 수 있다.

(현재 위치) mod 8 일 때 동일 -> (현재 위치) mod (5 - 1) * 2 = (현재 위치) mod (c - 1) * 2

이렇게 하면 방향 전환 하는 경우를 두 번만 고려하면 된다.

 

 

 

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
#include <iostream>
#include <algorithm>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
struct Node {
    int r;
    int c;
    int speed;
    int direction;
    int size;
};
int r, c, m, ans;
Node arr[101][101];
bool isSharkExist(int i, int j);
void removeShark(int i, int j);
void input();
void catchShark(int i, int j) {
    ans += arr[i][j].size;
    removeShark(i, j);
}
queue<Node> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
 
    // 1. 낚시왕이 오른쪽으로 한 칸 이동한다.
    rep(pos, c) {
        // 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.상어를 잡으면 격자판에서 잡은 상어가 사라진다.
        rep(row, r) {
            if (isSharkExist(row, pos)) {
                catchShark(row, pos);
                break;
            }
        }
        // 3. 상어가 이동한다.
        rep(row, r) {
            rep(col, c) {
                if (isSharkExist(row, col)) {
                    Node& now = arr[row][col];
                    int nr = row;
                    int nc = col;
                    int move = now.speed;
 
                    // 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.
                    // 1: 상, 2: 하, 3: 우, 4: 좌
                    if (now.direction == 1) {
                        move %= (r - 1) * 2;
                        nr = row - move;
                        if (nr < 0) {
                            now.direction = 2;
                            nr *= -1;
                            if (nr >= r) {
                                now.direction = 1;
                                nr = (r - 1) * 2 - nr;
                            }
 
                        }
                    }
                    else if (now.direction == 2) {
                        move %= (r - 1) * 2;
                        nr = row + move;
                        if (nr >= r) {
                            now.direction = 1;
                            nr = (r - 1) * 2 - nr;
                            if (nr < 0) {
                                now.direction = 2;
                                nr *= -1;
                            }
                        }
                    }
                    else if (now.direction == 3) {
                        move %= (c - 1) * 2;
                        nc = col + move;
                        if (nc >= c) {
                            now.direction = 4;
                            nc = (c - 1) * 2 - nc;
                            if (nc < 0) {
                                now.direction = 3;
                                nc *= -1;
                            }
                        }
                    }
                    else if (now.direction == 4) {
                        move %= (c - 1) * 2;
                        nc = col - move;
                        if (nc < 0) {
                            now.direction = 3;
                            nc *= -1;
                            if (nc >= c) {
                                now.direction = 4;
                                nc = (c - 1) * 2 - nc;
                            }
 
                        }
                    }
 
                    // 상어가 이동할 좌표를 구하고 난 뒤, 즉시 새 위치로 이동시키면 (arr[nr][nc])
                    // 원래 [nr][nc]에 있는 상어를 덮어쓰게 됨. 따라서, 해당 상어는 이동하지 못함.
                    // 이를 방지하기 위해서 상어의 새 좌표를 큐에 삽입한 뒤, 나중에 한 번에 이동시킴
                    q.push({ nr, nc, now.speed, now.direction, now.size });
 
                    // 이동 완료
                    removeShark(row, col);
                }
            }
        }
        // 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.
        while (!q.empty()) {
            Node now = q.front(); q.pop();
            arr[now.r][now.c] = (now.size > arr[now.r][now.c].size ? now : arr[now.r][now.c]);
        }
    }
    cout << ans;
}
 
bool isSharkExist(int i, int j) {
    Node now = arr[i][j];
    if (now.direction != 0 && now.size != 0) return true;
    return false;
}
void removeShark(int i, int j) {
    Node& now = arr[i][j];
    now.r = 0;
    now.c = 0;
    now.size = 0;
    now.direction = 0;
    now.speed = 0;
}
void input() {
    cin >> r >> c >> m;
    rep(i, m) {
        int a, b, s, d, z;
        cin >> a >> b >> s >> d >> z;
        arr[a - 1][b - 1] = { a - 1,b - 1,s,d,z };
    }
}
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17779 [복습 필수]  (0) 2021.08.06
백준 17142  (0) 2021.08.04
백준 5373 [복습필수]  (0) 2021.04.30
백준 16234  (0) 2021.04.30
백준 15683  (0) 2021.04.30
반응형

www.acmicpc.net/problem/5373

 

5373번: 큐빙

각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란

www.acmicpc.net

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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
enum {U, D, L, R, F, B};
char cube[6][3][3];
int t, n;
string cmd;
 
// 큐브 초기화
void init() {
    rep(i, 3) {
        rep(j, 3) {
            cube[U][i][j] = 'w';
            cube[D][i][j] = 'y';
            cube[L][i][j] = 'g';
            cube[R][i][j] = 'b';
            cube[F][i][j] = 'r';
            cube[B][i][j] = 'o';
        }
    }
}
 
// 큐브 출력
void print() {
    rep(i, 3) {
        rep(j, 3)
            cout << cube[U][i][j];
        cout << '\n';
    }
}
 
// 표면 회전
void rot(char surface, char dir) {
    char temp[3][3];
    int pos;
    if (surface == 'U')
        pos = U;
    else if (surface == 'F')
        pos = F;
    else if (surface == 'L')
        pos = L;
    else if (surface == 'B')
        pos = B;
    else if (surface == 'R')
        pos = R;
    else if (surface == 'D')
        pos = D;
    
    // 시계방향 회전
    if (dir == '+') {
        rep(i, 3) {
            temp[0][i] = cube[pos][2 - i][0];
            temp[2][i] = cube[pos][2 - i][2];
            temp[1][i] = cube[pos][2 - i][1];
        }
    }
    // 반시계방향 회전
    else {
        rep(i, 3) {
            temp[0][i] = cube[pos][i][2];
            temp[2][i] = cube[pos][i][0];
            temp[1][i] = cube[pos][i][1];
        }
    }
    rep(i, 3) {
        rep(j, 3)
            cube[pos][i][j] = temp[i][j];
    }
}
void func(string cmd) {
    char temp[3];
 
    // 표면 회전시킴
    rot(cmd[0], cmd[1]);
 
    // 윗면 시계방향일 때 인접한 면 회전
    if (cmd == "U+") {
        rep(i, 3)
            temp[i] = cube[F][0][i];
 
        rep(i, 3) 
            cube[F][0][i] = cube[R][0][i];
        rep(i, 3)
            cube[R][0][i] = cube[B][0][i];
        rep(i, 3)
            cube[B][0][i] = cube[L][0][i];
        rep(i, 3)
            cube[L][0][i] = temp[i];
    }
 
    // 윗면 반시계방향일 때 인접한 면 회전
    else if (cmd == "U-") {
        rep(i, 3)
            temp[i] = cube[F][0][i];
 
        rep(i, 3) 
            cube[F][0][i] = cube[L][0][i];
        rep(i, 3)
            cube[L][0][i] = cube[B][0][i];
        rep(i, 3)
            cube[B][0][i] = cube[R][0][i];
        rep(i, 3)
            cube[R][0][i] = temp[i];
    }
 
    // 아랫면 시계방향일 때 인접한 면 회전
    else if (cmd == "D+") {
        rep(i, 3)
            temp[i] = cube[F][2][i];
 
        rep(i, 3) 
            cube[F][2][i] = cube[L][2][i];
        rep(i, 3)
            cube[L][2][i] = cube[B][2][i];
        rep(i, 3)
            cube[B][2][i] = cube[R][2][i];
        rep(i, 3)
            cube[R][2][i] = temp[i];
    }
    // 아랫면 반시계방향일 때 인접한 면 회전
    else if (cmd == "D-") {
        rep(i, 3)
            temp[i] = cube[F][2][i];
 
        rep(i, 3)
            cube[F][2][i] = cube[R][2][i];
        rep(i, 3)
            cube[R][2][i] = cube[B][2][i];
        rep(i, 3)
            cube[B][2][i] = cube[L][2][i];
        rep(i, 3)
            cube[L][2][i] = temp[i];
    }
 
    // 왼쪽 시계방향일 때 인접한 면 회전
    else if (cmd == "L+") {
        rep(i, 3)
            temp[i] = cube[U][i][0];
 
        rep(i, 3) 
            cube[U][i][0] = cube[B][2-i][2];
        rep(i, 3)
            cube[B][i][2] = cube[D][2-i][0];
        rep(i, 3)
            cube[D][i][0] = cube[F][i][0];
        rep(i, 3)
            cube[F][i][0] = temp[i];
    }
 
    // 왼쪽 반시계방향일 때 인접한 면 회전
    else if (cmd == "L-") {
        rep(i, 3)
            temp[i] = cube[U][i][0];
 
        rep(i, 3) 
            cube[U][i][0] = cube[F][i][0];
        rep(i, 3)
            cube[F][i][0] = cube[D][i][0];
        rep(i, 3)
            cube[D][i][0] = cube[B][2-i][2];
        rep(i, 3)
            cube[B][i][2] = temp[2-i];
    }
 
    // 오른쪽 시계방향일 때 인접한 면 회전
    else if (cmd == "R+") {
        rep(i, 3)
            temp[i] = cube[U][i][2];
 
        rep(i, 3) 
            cube[U][i][2] = cube[F][i][2];
        rep(i, 3)
            cube[F][i][2] = cube[D][i][2];
        rep(i, 3)
            cube[D][i][2] = cube[B][2-i][0];
        rep(i, 3)
            cube[B][i][0] = temp[2-i];
    }
 
    // 오른쪽 반시계방향일 때 인접한 면 회전
    else if (cmd == "R-") {
        rep(i, 3)
            temp[i] = cube[U][i][2];
 
        rep(i, 3) 
            cube[U][i][2] = cube[B][2-i][0];
        rep(i, 3)
            cube[B][i][0] = cube[D][2-i][2];
        rep(i, 3)
            cube[D][i][2] = cube[F][i][2];
        rep(i, 3)
            cube[F][i][2] = temp[i];
        
    }
 
    // 앞면 시계방향일 때 인접한 면 회전
    else if (cmd == "F+") {
        rep(i, 3)
            temp[i] = cube[U][2][i];
 
        rep(i, 3) 
            cube[U][2][i] = cube[L][2-i][2];
        rep(i, 3)
            cube[L][i][2] = cube[D][0][i];
        rep(i, 3)
            cube[D][0][i] = cube[R][2-i][0];
        rep(i, 3)
            cube[R][i][0] = temp[i];
        
    }
 
    // 앞면 반시계방향일 때 인접한 면 회전
    else if (cmd == "F-") {
        rep(i, 3)
            temp[i] = cube[U][2][i];
 
        rep(i, 3) 
            cube[U][2][i] = cube[R][i][0];
        rep(i, 3)
            cube[R][i][0] = cube[D][0][2-i];
        rep(i, 3)
            cube[D][0][i] = cube[L][i][2];
        rep(i, 3)
            cube[L][i][2] = temp[2-i];
    }
 
    // 뒷면 시계방향일 때 인접한 면 회전
    else if (cmd == "B+") {
        rep(i, 3)
            temp[i] = cube[U][0][i];
 
        rep(i, 3)
            cube[U][0][i] = cube[R][i][2];
        rep(i, 3)
            cube[R][i][2] = cube[D][2][2-i];
        rep(i, 3)
            cube[D][2][i] = cube[L][i][0];
        rep(i, 3)
            cube[L][i][0] = temp[2-i];
 
    }
 
    // 뒷면 반시계방향일 때 인접한 면 회전
    else if (cmd == "B-") {
        rep(i, 3)
            temp[i] = cube[U][0][i];
 
        rep(i, 3) 
            cube[U][0][i] = cube[L][2-i][0];
        rep(i, 3)
            cube[L][i][0] = cube[D][2][i];
        rep(i, 3)
            cube[D][2][i] = cube[R][2-i][2];
        rep(i, 3)
            cube[R][i][2] = temp[i];
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        init();
        cin >> n;
        rep(i, n) {
            cin >> cmd;
            func(cmd);
        }
        print();
    }
}
cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17142  (0) 2021.08.04
백준 17143  (0) 2021.07.19
백준 16234  (0) 2021.04.30
백준 15683  (0) 2021.04.30
백준 13458  (0) 2021.04.29
반응형

www.acmicpc.net/problem/16234

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

1
2
3
4
5
6
7
8
    bool flag = true;
    while (flag) {
        memset(visited, 0, sizeof(visited));
        flag = bfs();
        if(flag)
            ans++;
    }
    cout << ans;
 cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    rep(k, 4) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
        int gap = abs(arr[x][y] - arr[nx][ny]);        
        if (gap >= l && gap <= r) {    // 차이가 L 이상 R 이하이면
            visited[nx][ny] = 1;    // 방문처리
            q.push({ nx, ny });
            sum += arr[nx][ny];        // 인구수 더하기
            cnt++;                    // 연합 도시 숫자 추가
            v.push_back({ nx, ny });
        }
    }
}
 cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 연합 있으면
if (cnt > 1) {
    ret = true;
                    
    int tmp = sum / cnt;
    // 연합 도시 인구수 갱신
    for (pii p : v) {
        int px = p.first;
        int py = p.second;
        arr[px][py] = tmp;
    }
}
sum = 0;
cnt = 0;
v.clear();
 cs

 

 

 

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
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define pii pair<int, int>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, l, r, arr[51][51], ans, sum, cnt;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
bool visited[51][51];
queue<pii> q;
vector<pii> v;
bool bfs() {
    bool ret = false;
    rep(i, n) {
        rep(j, n) {
            if (!visited[i][j]) {
                visited[i][j] = 1;
                sum += arr[i][j];
                cnt++;
                v.push_back({ i,j });
                q.push({ i,j });
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    rep(k, 4) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
                        int gap = abs(arr[x][y] - arr[nx][ny]);        
                        if (gap >= l && gap <= r) {    // 차이가 L 이상 R 이하이면
                            visited[nx][ny] = 1;    // 방문처리
                            q.push({ nx, ny });
                            sum += arr[nx][ny];        // 인구수 더하기
                            cnt++;                    // 연합 도시 숫자 추가
                            v.push_back({ nx, ny });// 연합 도시 좌표 추가
                        }
                    }
                }
                // 연합 있으면
                if (cnt > 1) {
                    ret = true;
                    
                    int tmp = sum / cnt;
                    // 연합 도시 인구수 갱신
                    for (pii p : v) {
                        int px = p.first;
                        int py = p.second;
                        arr[px][py] = tmp;
                    }
                }
                sum = 0;
                cnt = 0;
                v.clear();
            }
        }
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> l >> r;
    rep(i, n) {
        rep(j, n)
            cin >> arr[i][j];
    }
    bool flag = true;
    while (flag) {
        memset(visited, 0, sizeof(visited));
        flag = bfs();
        if(flag)
            ans++;
    }
    cout << ans;
}
 cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 17143  (0) 2021.07.19
백준 5373 [복습필수]  (0) 2021.04.30
백준 15683  (0) 2021.04.30
백준 13458  (0) 2021.04.29
백준 3190  (0) 2021.04.29
반응형

www.acmicpc.net/problem/15683

 

15683번: 감시

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void dfs(int x, int y, int idx) {
    if (idx == cnt) {
        ans = min(ans, zeros());
        return;
    }
    int rotate = 4;
    int i = cctvs[idx].first;
    int j = cctvs[idx].second;
    int cctv = arr[i][j];
 
    if (cctv == -2)
        rotate = 2;
 
    else if (cctv == -5)
        rotate = 1;
 
    rep(k, rotate) {
        look(i, j, cctv, k, 1);
        visited[i][j] = 1;
        dfs(i, j, idx+1);
        visited[i][j] = 0;
        look(i, j, cctv, k, 0);
    }
}
 cs

 

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
void look(int x, int y, int cctv, int direction, int cmd) {
    // direction: 0, 1, 2, 3
    if (cctv == -1) {
        lookDirection(x, y, direction, cmd);
    }
    // direction: 0, 1
    else if (cctv == -2) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction+2)%4, cmd);
    }
 
    // direction: 0, 1, 2, 3
    else if (cctv == -3) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction + 1) % 4, cmd);
    }
 
    // direction: 0, 1, 2, 3
    else if (cctv == -4) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction + 1) % 4, cmd);
        lookDirection(x, y, (direction + 2) % 4, cmd);
    }
 
    // direction: 
    else if (cctv == -5) {
        lookDirection(x, y, 0, cmd);
        lookDirection(x, y, 1, cmd);
        lookDirection(x, y, 2, cmd);
        lookDirection(x, y, 3, cmd);
    }
}
 cs

 

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
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m, arr[9][9], temp, ans= 987654321;
pii cctvs[9];
int cnt;
bool visited[9][9];
void lookDirection(int x, int y, int direction, int cmd) {
    while (x >= 0 && x < n && y >= 0 && y < m) {
        if (arr[x][y] == -6) break;
        if (arr[x][y] < 0) {
            if (direction == 0) y++;
            else if (direction == 1) x++;
            else if (direction == 2) y--;
            else if (direction == 3) x--;
            continue;
        }
        // 우
        if (direction == 0) {
            if (cmd)
                arr[x][y++]++;
            else
                arr[x][y++]--;
        }
        // 하
        else if (direction == 1) {
            if (cmd)
                arr[x++][y]++;
            else
                arr[x++][y]--;
        }
        // 좌
        else if (direction == 2) {
            if (cmd)
                arr[x][y--]++;
            else
                arr[x][y--]--;
        }
        // 상
        else if (direction == 3) {
            if (cmd)
                arr[x--][y]++;
            else
                arr[x--][y]--;
        }
    }
}
void look(int x, int y, int cctv, int direction, int cmd) {
    // direction: 0, 1, 2, 3
    if (cctv == -1) {
        lookDirection(x, y, direction, cmd);
    }
    // direction: 0, 1
    else if (cctv == -2) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction+2)%4, cmd);
    }
 
    // direction: 0, 1, 2, 3
    else if (cctv == -3) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction + 1) % 4, cmd);
    }
 
    // direction: 0, 1, 2, 3
    else if (cctv == -4) {
        lookDirection(x, y, direction, cmd);
        lookDirection(x, y, (direction + 1) % 4, cmd);
        lookDirection(x, y, (direction + 2) % 4, cmd);
    }
 
    // direction: 
    else if (cctv == -5) {
        lookDirection(x, y, 0, cmd);
        lookDirection(x, y, 1, cmd);
        lookDirection(x, y, 2, cmd);
        lookDirection(x, y, 3, cmd);
    }
}
int zeros() {
    int ret = 0;
    rep(i, n) {
        rep(j, m)
            if (arr[i][j] == 0) ret++;
    }
    return ret;
}
void dfs(int x, int y, int idx) {
    if (idx == cnt) {
        ans = min(ans, zeros());
        return;
    }
    int rotate = 4;
    int i = cctvs[idx].first;
    int j = cctvs[idx].second;
    int cctv = arr[i][j];
 
    if (cctv == -2)
        rotate = 2;
 
    else if (cctv == -5)
        rotate = 1;
 
    rep(k, rotate) {
        look(i, j, cctv, k, 1);
        visited[i][j] = 1;
        dfs(i, j, idx+1);
        visited[i][j] = 0;
        look(i, j, cctv, k, 0);
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, n) {
        rep(j, m) {
            cin >> temp;
            arr[i][j] = temp * -1;            // arr[i][j]: cctv가 감시 가능한 영역이면 + 1
            if(temp>=1&&temp<=5)            // cctv 번호, 벽과 겹칠 수 있으므로, (입력) * -1 해서 음수로 저장
                cctvs[cnt++] = { i,j };
        }
    }
    dfs(0, 0, 0);
    cout << ans;
}
cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 5373 [복습필수]  (0) 2021.04.30
백준 16234  (0) 2021.04.30
백준 13458  (0) 2021.04.29
백준 3190  (0) 2021.04.29
백준 13460  (0) 2021.03.07
반응형

www.acmicpc.net/problem/13458

 

13458번: 시험 감독

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

www.acmicpc.net

 

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
#include <iostream>
#define ll long long
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
ll n, arr[1000001], b, c, ans;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    rep(i, n)
        cin >> arr[i];
 
    cin >> b >> c;
    rep(i, n) {
        // 총 감독관
        arr[i] -= b;
        ans++;
 
        // 부 감독관
        if (arr[i] > 0) {
            ll temp = (arr[i] / c);
            arr[i] -= temp * c;
            ans += temp;
            if (arr[i] > 0)
                ans++;
        }
    }
    cout << ans;
}
cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 16234  (0) 2021.04.30
백준 15683  (0) 2021.04.30
백준 3190  (0) 2021.04.29
백준 13460  (0) 2021.03.07
백준 12100 [복습 필수]  (0) 2021.03.03

+ Recent posts

티스토리툴바