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

 

1347번: 미로 만들기

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다. 입력으로 홍준이가 적은 내용이 주어진다. 문자열로 이루어져 있으며, 모든 문자 하나는

www.acmicpc.net

문제에서 홍준이는 자기의 움직임을 모두 적는다. 홍준이가 적은 내용의 길이 N이과 그 내용이 주어진다.

미로가 몇 칸인지 알 수 없으므로 미로를 만들 배열의 크기를 101*101로 잡았다.

문제에서 N이 0보다 크고 50보다 작다고 했으므로 상하좌우 어떤 방향이든 한 방향으로만 가는 경우(가장 멀리 가는 경우)를 생각해서 넉넉하게 잡았다.

 

 

시작점은 배열의 가운데 쯤인 50,50에서 시작하면서 적은 내용에 맞게 움직인다.

처음에 남쪽을 바라보고 있다고 했으므로 처음 방향은(1,0)이다.

방향 전환을 쉽게 할 수 있도록 dx, dy배열에 남쪽에서부터 시계방향 순서로(반대도 상관없다) 방향을 저장해 둔다.

R 인 경우 오른쪽으로 방향을 전환하므로 dir+1을 해주면 되지만 3번째는 index를 넘어가버리기 때문에 % 연산을

이용하여 (dir+1) % 4를 해주면 된다.

마찬가지로 L은 왼쪽 방향으로 회전하므로 dx, dy배열의 앞의 칸으로 이동하기 위해 (dir+3) % 4를 해주면 된다.

 

 

가장 중요한 직사각형 미로를 출력해주기 위해서 직사각형의 시작점과 끝점을 알아야 한다.

시작점과 끝점을 홍준이의 시작 위치(50,50)로 잡아두고 이동할 때마다 비교해서

x, y의 최솟값(왼쪽 맨 위)이 시작점, x,y의 최댓값(오른쪽 맨 아래)이 끝점이 되도록 해준다.

 

 

그러면 내용대로 모두 움직인 후에 직사각형 범위만큼을 출력해주면 되는데

. 이 없는 경우에 #을 출력하면 된다.

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
#include <iostream>
#include <string>
using namespace std;
 
 
int n;
string s;
char map[101][101];
 
//남,서,북,동 순서
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };
 
 
void solve() {
    //직사각형의 왼쪽 위 좌표(sx,sy)와 오른쪽 아래 좌표(ex,ey)
    int sx = 50;
    int sy = 50;
    int ex = 50;
    int ey = 50;
 
 
    //시작점을 가운데 칸으로 설정
    int x = 50;
    int y = 50;
    int dir = 0;
    map[x][y] = '.';
 
 
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') {
            //오른쪽으로 방향 회전
            dir = (dir + 1) % 4;
        }
        else if (s[i] == 'L') {
            //왼쪽으로 방향 회전
            dir = (dir + 3) % 4;
        }
        else if (s[i] == 'F') {
            //앞으로 이동
            x += dx[dir];
            y += dy[dir];
            map[x][y] = '.';
 
 
            //이동한 경우 직사각형의 좌표와 비교해준다.
            if (x < sx) sx = x;
            if (y < sy) sy = y;
            if (x > ex) ex = x;
            if (y > ey) ey = y;
        }
 
        
    }
 
 
    //직사각형을 출력
    // '.' 이 아닌 경우에는 벽이므로 '#'을 출력
    for (int i = sx; i <= ex; i++) {
        for (int j = sy; j <= ey; j++) {
            if (map[i][j] == '.')
                cout << map[i][j];
            else
                cout << '#';
        }
        cout << '\n';
    }
 
    
 
}
 
int main() {
 
    cin >> n;
    cin >> s;
 
    solve();
    
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2638. 치즈  (0) 2019.07.08
[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 14620. 꽃길  (0) 2019.07.06
[BOJ] 14889. 스타트와 링크  (0) 2019.07.06
[BOJ] 3184. 양  (0) 2019.07.06

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

 

14620번: 꽃길

2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수

www.acmicpc.net

화단에 씨앗 세 개를 심어서 1년 후 세 씨앗 모두 꽃잎이 만개하도록 씨앗의 위치를 정해줘야 하는 문제이다.

그리고 꽃이 피는 화단의 비용이 최소여야한다.

 

테두리 부분(씨앗을 심으면 화단을 넘어가는 부분)을 제외하고 모든 칸에서 씨앗을 심는 경우를 구해준다.

심을 칸과 심을 칸의 상하좌우 부분(꽃이 피는 부분)에 이미 다른 꽃이 있으면 그 칸은 씨앗을 심지 않고 넘어간다.

 

씨앗을 심을 수 있다면, 심은 것을 체크해주고 다음으로 씨앗을 심을 곳을 정해준다.

세 개의 씨앗을 심을 곳을 모두 정해줬다면 꽃이 피는 땅의 비용을 계산해서 최솟값과 비교해준다.

 

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
#include <iostream>
using namespace std;
 
int n, ans;
int cost[10][10];
bool check[10][10];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int calc() {
    int sum = 0 ;
    int cnt = 0;
 
    //꽃이 펴있는 칸을 계산
    //꽃 세개가 차지하는 칸은 15개이므로 꽃이 있는 모든 칸의 비용을 더해줬다면 탐색을 중단 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j]) {
                sum += cost[i][j];
                cnt++;
                if (cnt == 15) return sum;
            }
        }
    }
}
 
 
 
//씨앗을 심을 땅을 골라준다.
void select(int cnt) {
    if (cnt == 3) {
        // 세 씨앗을 모두 심었으면 비용을 계산
        int tmp = calc();
        if (ans == -1 || ans > tmp)
            ans = tmp;
 
        return;
    }
 
    
 
    //모든 땅에 대해서 꽃을 심어본다.
    //꽃이 화단 밖으로 나가면 죽으므로 피었을때 화단 밖으로 나가는 경우(테두리 부분)는 제외한다.
    for (int i = 1; i < n - 1; i++) {
 
        for (int j = 1; j < n - 1; j++) {
 
            //꽃이 피는 곳에 다른 꽃 없는지 체크
            bool flag = true;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
 
                //꽃이 피어야하는 곳에 이미 다른 꽃이 있다면 해당 칸에는 꽃을 심을 수 없다.
                if (check[nx][ny]) {
                    flag = false;
                    break;
                }
            }
 
 
            
            //꽃이 죽을 것이므로 다음 칸에 심는 경우로 넘어간다.
            if (!flag) continue;
 
 
 
            //i,j칸에 씨앗을 심는 경우
            //꽃이 필 수 있는 경우 꽃이 피는 자리를 표시해둔다.
            check[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                check[nx][ny] = true;
            }
 
 
            //현재 i,j칸에서 꽃을 심는 것으로 고른 후 하나를 더 심는 경우로 넘어간다.
            select(cnt + 1);
 
 
            //i,j칸에 꽃을 심는 경우가 끝났으므로 다시 false 표시해준다.
            check[i][j] = false;
            for (int k = 0; k < 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                check[nx][ny] = false;
            }
 
 
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> cost[i][j];
        }
    }
 
    ans = -1;
 
    select(0);
 
    cout << ans;
    return 0;
 
 
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2636. 치즈  (0) 2019.07.08
[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14889. 스타트와 링크  (0) 2019.07.06
[BOJ] 3184. 양  (0) 2019.07.06
[BOJ] 1026. 보물  (0) 2019.07.06

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

각 팀원들의 능력치가 주어지고 두 팀의 능력치 차이가 최소가 되는 팀을 구해서

그 차이 값을 출력하는 문제이다.

 

 

 N(4 ≤ N ≤ 20, N은 짝수)이므로 팀원을 나누는 모든 경우를 해보는 완전 탐색으로 풀어줄 수 있다.

N명의 팀원을 1번 팀에 들어가는 경우와 2번 팀에 들어가는 경우를 모두 해준다.

단, 모든 팀원들의 팀을 정했을 때 팀원이 N/2가 아닌 경우는 계산해주지 않는다(return)

이 부분을 제대로 처리해주지 않아서 오류가 났었다...ㅠ

능력치를 계산해주는 부분에서 vector의 index를 넘어갔기 때문이다.

 

 

모든 팀원의 팀을 정해주었고, 각 팀에 N/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
#include <iostream>
#include <vector>
using namespace std;
 
int n, ans;
int s[20][20];
 
vector<int> t1;
vector<int> t2;
 
int calc() {
    int diff;
    int t1sum = 0;
    int t2sum = 0;
 
    //각 팀의 능력치의 합을 구해준다.
    for (int i = 0; i < n/2; i++) {
        for (int j = 0; j < n/2; j++) {
            if (i == j) continue;
            t1sum += s[t1[i]][t1[j]];
            t2sum += s[t2[i]][t2[j]];
        }
    }
 
 
    //차이를 구한 후 차이 값을 리턴
    diff = t1sum - t2sum;
    if (diff < 0) diff = -diff;
 
    return diff;
}
 
 
//팀을 골라준다.
void select(int index) {
 
    //팀을 모두 고른 경우
    if (index == n) {
        //각 팀은 N/2명이어야 하므로 그렇지 않은 경우 리턴
        if (t1.size() > n / 2) return;
        if (t2.size() > n / 2) return;
 
 
        //각 팀의 능력치 차이를 계산해서 최소값과 비교한다.
        int tmp = calc();
        if (ans == -1 || ans > tmp) ans = tmp;
        
        return;
    }
 
 
    //index번째를 첫번쨰 팀에 넣는 경우
    t1.push_back(index);
    select(index + 1);
    t1.pop_back();
 
 
    //index번째를 두번째 팀에 넣는 경우
    t2.push_back(index);
    select(index + 1);
    t2.pop_back();
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    }
 
 
    ans = -1;
    select(0);
 
    cout << ans;
 
    return 0;
}
 
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1347. 미로 만들기  (0) 2019.07.06
[BOJ] 14620. 꽃길  (0) 2019.07.06
[BOJ] 3184. 양  (0) 2019.07.06
[BOJ] 1026. 보물  (0) 2019.07.06
[BOJ] 2210. 숫자판 점프  (0) 2019.07.03

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

 

3184번: 양

문제 미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다. 마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지

www.acmicpc.net

마당에 영역별로 양과 늑대가 있는데, 같은 영역 안에서 양이 늑대보다 더 많으면 싸워서 이길 수 있다.

마지막에 살아남은 양과 늑대의 수를 출력하는 문제이다.

 

먼저 각 영역에서의 양의 수와 늑대의 수를 구하기 위해서 bfs를 이용했다. bfs를 통해 연결된 영역을 구하면서

양이나 늑대가 있는 경우에 숫자를 카운트한다.

 

한 영역의 탐색이 끝난 후에 양의 수와 늑대의 수를 비교해준다.

양의 수가 많은 경우 전체 양의 수에 해당 영역의 양의 수를 더해준다.

그렇지 않은 경우 늑대의 수를 전체 늑대의 수에 더해주면 된다.

 

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
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
 
int r, c, sheep, wolf;
bool check[250][250];
char map[250][250];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    check[x][y] = true;
 
    int ocnt = 0;
    int vcnt = 0;
 
    //출발점이 양이나 늑대인 경우
    if (map[x][y] == 'o') {
        ocnt++;
    }
    else if (map[x][y] == 'v') {
        vcnt++;
    }
 
    while (!q.empty()) {
        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 >= r || ny >= c) continue;
            
            //방문체크
            if (check[nx][ny]) continue;
 
            //울타리
            if (map[nx][ny] == '#') continue;
            
            q.push(make_pair(nx, ny));
            check[nx][ny] = true;
 
            //이동하는 곳에 양이 있는 경우 양의 수 증가
            if (map[nx][ny] == 'o') {
                ocnt++;
            }//이동하는 곳에 늑대가 있는 경우 늑대의 수 증가
            else if (map[nx][ny] == 'v') {
                vcnt++;
            }
        }
    }
 
 
    //탐색이 끝난 후에 양의 수가 더 많으면 양의 수를 전체 양의 수에 더한다.(양이 살아 남음)
    if (ocnt > vcnt) {
        sheep += ocnt;
    }
    else {//늑대의 수가 더 많거나 같은 경우 늑대가 살아남는다.
        wolf += vcnt;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> map[i][j];
        }
    }
 
 
 
    //영역별로 bfs를 실행
    //방문한 곳(다른 영역)이나 울타리는 탐색하지 않는다.
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] == '#') continue;
            if (check[i][j]) continue;
            bfs(i, j);
        }
    }
 
 
    cout << sheep << ' ' << wolf;
    
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14620. 꽃길  (0) 2019.07.06
[BOJ] 14889. 스타트와 링크  (0) 2019.07.06
[BOJ] 1026. 보물  (0) 2019.07.06
[BOJ] 2210. 숫자판 점프  (0) 2019.07.03
[BOJ] 13458. 시험 감독  (0) 2019.07.03

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

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

www.acmicpc.net

간단한 정렬 문제이다.

a배열과 b배열의 각 원소를 곱한 값을 모두 더한 값이 최소가 되어야 하는 a배열의 수만 재배열해야 한다.

이 값이 최소가 되기 위해서 a의 가장 큰 값과 b의 가장 작은 값을 곱하고 b의 가장 큰값과 a의 가장 작은 값을 곱해주는 방법을 사용하였다.

 

a배열만 재배열해야 한다고 문제에 나와있지만, 정답으로 합만 출력하면 되므로 a와 b 모두 정렬해줬다.

a와 b 모두 오름차순으로 정렬 후에 a배열의 맨 앞의 값(최솟값)과 b배열의 맨 뒤의 값(최댓값)을 곱해준다.

a배열의 인덱스는 증가하고 b배열의 인덱스는 감소시켜서 점점 a의 큰 값과 b의 작은 값을 곱하도록 한다.

 

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>
using namespace std;
 
int n, sum;
int a[51];
int b[51];
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    cin >> n;
 
 
    //input
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
 
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
 
 
    //a와 b를 정렬
    sort(a, a + n);
    sort(b, b + n);
    
 
    //a는 가장 작은 수부터 b는 가장 큰수부터해서 각각 곱해준다.
    for (int i = 0, j = n - 1; i < n; i++, j--) {
        sum += a[i] * b[j];
    }
 
 
    cout << sum;
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 14889. 스타트와 링크  (0) 2019.07.06
[BOJ] 3184. 양  (0) 2019.07.06
[BOJ] 2210. 숫자판 점프  (0) 2019.07.03
[BOJ] 13458. 시험 감독  (0) 2019.07.03
[BOJ] 2529. 부등호  (0) 2019.07.03

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

 

2210번: 숫자판 점프

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

www.acmicpc.net

이동하는 칸에 있는 숫자를 합쳐서 서로 다른 6자리의 수를 만드는 문제이다.

set을 사용하면 중복을 제거하여 서로 다른 수를 쉽게 만들 수 있다.

 

먼저 모든 칸에서 네 방향으로 움직여본다.

중복이 가능해서 오래 걸릴 것 같지만 시간 복잡도를 대충 계산해보면

5*5 (모든 칸에서 시작) * 4^5 (네가지 방향으로 다섯 번 이동) 이므로 생각보다 적다.

 

이동할 때마다 현재 숫자에 곱하기 10을 해줘서 자릿수를 앞으로 당겨주고 현재 칸의 값을 더해준다.

예를 들어 123이었고 현재 칸이 4라면 123*10 + 4를 해줘서 1234를 만들 수 있다.

 

5번 이동을 마치고 6자리 숫자가 되었다면 set에 추가해준다.

모든 칸에 대해서 이동을 마쳤다면 set의 사이즈(서로 다른 6자리수의 개수)를 출력해주면 된다.

 

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
#include <iostream>
#include <set>
using namespace std;
 
int map[5][5];
set<int> s;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void solve(int x, int y, int cnt, int num) {
    //다섯번 이동했으면 합친 숫자를 set에 넣어준다.
    if (cnt >= 5) {
        s.insert(num);
        return;
    }
 
 
    //네 방향으로 이동
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
 
        //기존의 숫자에 10을 곱해준뒤 현재 칸의 숫자를 더해준다.
        solve(nx, ny, cnt + 1, num*10+map[nx][ny]);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> map[i][j];
        }
    }
 
    //모든 점에서 출발해본다.
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            solve(i, j, 0, map[i][j]);
        }
    }
 
 
    //set의 크기를 출력
    cout << s.size();
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 3184. 양  (0) 2019.07.06
[BOJ] 1026. 보물  (0) 2019.07.06
[BOJ] 13458. 시험 감독  (0) 2019.07.03
[BOJ] 2529. 부등호  (0) 2019.07.03
[BOJ] 1748. 수 이어 쓰기 1  (0) 2019.07.03

https://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명 혹은 여러 명의 부감독관이 있는데 각 시험장마다 응시생들을 모두 감시해야 한다.

이때, 필요한 감독관 수의 최솟값을 구하는 문제이다.

 

문제를 읽고 총감독관이 없어도 되는건가? 하고 헷갈렸는데 1명은 있어야 맞는 것 같다.

그러므로 일단 각 시험장에서 총감독관이 감시할 수 있는 B명을 빼준다. 그리고 남은 인원을 부감독관이 감시하면 된다.

남은 인원 / 부감독관이 감시할 수 있는 인원

을 해주었을 때 나머지가 존재 할 수 있으므로 이런 경우에는 1을 더해준다.

 

 

이 문제에서 제일 중요한 점은 감독관의 수를 저장해 줄 변수를 long long으로 선언해주어야 한다는 것이다.

 

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

범위가 위와 같기 때문에 최악의 경우

B와 C가 1 , N이 1,000,000 , 모든방의 응시자 수 1,000,000 라면

1,000,000 (시험장의 개수) * 1,000,000 (응시자의 수) / (1+1) (b와 C)

가 되므로 int의 범위를 넘어가버리기 때문에 long long으로 선언해주어야 한다.

 

문제가 어렵지 않음에도 불구하고 정답률이 낮은건 이 부분 때문인 것 같다.

 

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
#include <iostream>
using namespace std;
int n;
int a[1000001];
int b, c;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
 
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> b >> c;
    
 
    //시험장의 개수 만큼 총감독관이 존재한다.
    long long ans = n;
    
    for (int i = 0; i < n; i++) {
        //총감독이 감시할 수 있는 인원을 제외
        a[i] -= b;
 
        //총감독이 i번쨰 시험장의 사람들을 모두 감시할 수 있으면
        //부감독관이 더 필요없으므로 넘어간다.
        if (a[i] <= 0) continue;
 
        //남은 인원을 부감독관이 감시할 수 있는 수로 나눠서 몇명이 더 필요한지 구한다.
        ans += a[i] / c;
 
        //나누어 떨어지지 않는 경우 1명이 더 필요하다.
        if (a[i] % c != 0) {
            ans += 1;
        }
    }
    
    cout << ans;
    return 0;
}
 
Colored by Color Scripter
  
 
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 1026. 보물  (0) 2019.07.06
[BOJ] 2210. 숫자판 점프  (0) 2019.07.03
[BOJ] 2529. 부등호  (0) 2019.07.03
[BOJ] 1748. 수 이어 쓰기 1  (0) 2019.07.03
[BOJ] 1107. 리모컨  (0) 2019.07.03

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

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.  A =>  < < < > < < > < > 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.  3 < 4 < 5 <

www.acmicpc.net

주어지는 부등호에 맞는 순열 중 최솟값과 최댓값을 찾는 문제이다.

각 부등호의 앞뒤 숫자만 맞으면 된다.

 

이 문제는 permutation을 써서 쉽게 구할 수 있다.

최댓값은 9876543210부터 시작하여 이전 순열을 구해서 찾아주고

최솟값은 0123456789부터 시작하여 다음 순열을 구해서 매번 부등호를 만족하는지 검사해주면 된다.

식을 만족하면 바로 출력해주고 break 해줘서 더 이상 다음 순열을 구하지 않는다.

 

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
char arr[9];
int n;
vector<int> num;
 
bool check() {
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (arr[i] == '<') {
            if (num[i] > num[i + 1]) {
                ok = false;
                break;
            }
        }
        else {
            if (num[i] < num[i + 1]) {
                ok = false;
                break;
            }
        }
    }
 
    return ok;
}
 
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
 
    //9부터 0까지 넣는다.
    for (int i = 9; i >= 0; i--) {
        num.push_back(i);
    }
 
 
    //최댓값을 구하기 위해 9876543210부터 이전 순열을 구한다.
    do {
        
        //식을 만족하면 print하고 break
        if (check()) {
            for (int i = 0; i <= n; i++) {
                cout << num[i];
            }
            cout << '\n';
            break;
        }
    } while (prev_permutation(num.begin(), num.end()));
 
 
    //벡터를 정리해준뒤에 0부터 9로 다시 채워넣는다.
    num.clear();
    for (int i = 0; i < 10; i++) {
        num.push_back(i);
    }
 
    //최솟값을 구하기 위해 0123456789부터 다음순열을 구한다.
    do {
 
        if (check()) {
            for (int i = 0; i <= n; i++) {
                cout << num[i];
            }
            cout << '\n';
            break;
        }
    } while (next_permutation(num.begin(), num.end()));
 
    
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2210. 숫자판 점프  (0) 2019.07.03
[BOJ] 13458. 시험 감독  (0) 2019.07.03
[BOJ] 1748. 수 이어 쓰기 1  (0) 2019.07.03
[BOJ] 1107. 리모컨  (0) 2019.07.03
[BOJ] 14442. 벽 부수고 이동하기 2  (0) 2019.06.28

+ Recent posts

티스토리툴바