728x90

시험 감독

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

문제

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000)

출력

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

삼섬SW역량테스트 기출문제 4번째

시험감독이라는 문제!

 

이번문제는 생각보다 빨리 풀었다. 문제를 풀어보면 알겠지만 쉬운문제다... 빨리 풀었다고 하기 민망하네..

근데 제출했는데 계속 틀렸데!! 아무리 봐도 다맞는데 테스트케이스 다 정답떳는데 뭐지?! 하고 봤다가

최대 시험장의수(1,000,000) x 각 시험장의 최대 응시자수(1,000,000) = 1,000,000,000,000 으로 INT 범위 초과!! 발생

 

문제도 쉬웠으니까 INT 범위에 대해서 간략하게 써보자. C++은 int 의 최대 범위가 21억..얼마정도이다. 정확히는

2,147,483,647 보통 문제에서는 #include <limits.h> 를 이용해서 INT_MAX 이거나 #define MAX 1e9 이거나 사용하는데

이번문제는 그 범위를 초과한다. 그럼 long long의 최대 값는 얼마냐면 9,223,372,036,854,775,808이다.

따라서 문제에서 요구하는 최대 범위를 충분히 표현할 수 있으므로 가능하다.

 

생각해보면 체점할때 1% 도 안올라가고 틀렸다고 나오는게  INT 범위를 초과하는 수를 알 수있냐 물어보는 듯 싶다.

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>
#define MAX 1000001
using namespace std;
//n : 시험장의수  
//b : 총감독관이 감시할수있는 응시생의 수 (총감응수)
//c : 부감독관이 감시할수있는 응시생의 수 (부감응수)
int n, b, c ;
int room[MAX];
long long ans;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> room[i];
    }
    cin >> b >> c;
    //1. 총감독관은 반드시 1명씩 들어가야한다.
    for (int i = 0; i < n; i++)
    {
        ans++;
        room[i] -= b;
    }
    //2. (남은 응시생수) / (부감응수)
    while (true)
    {
        bool flag = false;
        int cnt=0;
        for (int i = 0; i < n; i++)
        {
            if (room[i] <= 0)
                cnt++;
        }
        if (cnt == n)
            flag = true;
        if (flag)
            break;
        for (int i = 0; i < n; i++)
        {
            if (room[i] > 0)
            {
                int tmp1 = room[i] / c;
                int tmp2 = room[i] % c;
                ans += tmp1;
                if (tmp2 != 0)
                    ans++;
                room[i] = 0;
            }
        }
    }
 
    cout << ans;
    return 0;
}
 cs

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[구현, BOJ-14500] 테트로미노, c++  (0) 2021.05.13
[simulation, BOJ-14499] 주사위 굴리기, c+  (0) 2021.05.12
[Implementation, BOJ-3190] 뱀, c++  (0) 2021.05.11
[Simulation, BOJ-12100] 2048(Easy), c++  (0) 2021.05.10
[graph theory, BOJ-13460] 구슬 탈출2, c++  (0) 2021.05.09
728x90

뱀

문제

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데,  정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

삼성 SW 기출문제 3번째 문제 "뱀" 이라는 문제이다

queue 를 이용하여 {y,x}를 집어 넣어주었고

종료 조건으로 1. 몸통을 만났을때, 2. 벽을 만났을때 이렇게 설정하였다.

코드가 좀 지저분해서 고치고 싶은데 고칠시간에 한문제 더 푸는게 좋을거 같아서 여기서 끝.

아, 중간에 map을 print해가면서 초 단위로 움직임을 직접 보면서 디버깅하니까 좋았다.

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
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, l, ans;
int map[101][101];
//움직임을 담는 vector (sec, dir)
vector<pair<int, char>> moves;
//뱀의 좌표를 담는 queue (y, x)
queue<pair<int, int>> q;
//우, 좌, 하, 상
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
 
bool move(int y, int x)
{
    //1. 범위안에 있고
    if (y >= 1 && x >= 1 && y <= n && x <= n)
    {
        //2. 앞에 사과가 있을때
        if (map[y][x] == 2)
        {
            map[y][x] = 1;
            q.push({ y,x });
            ans++;
            return true;
        }
        //3. 아무것도 없을때
        else if (map[y][x] == 0)
        {
            map[y][x] = 1;
            q.push({ y,x });
            int fy = q.front().first;
            int fx = q.front().second;
            q.pop();
            map[fy][fx] = 0;
            ans++;
            return true;
        }
        //4. 자기 자신이 있을때
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
void bfs(int y, int x)
{
    q.push({ y,x });
    map[y][x] = 1;
    int dir = 0;
    while (true)
    {
        int ny = y + dy[dir];
        int nx = x + dx[dir];
        
        if (move(ny,nx))
        {
            /*
            cout << endl;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    cout << map[i][j] << ' ';
                }
                cout << endl;
            }
            cout << endl;
            */
            y = ny; x = nx;
            if (moves.size() > 0)
            {
                for (int i = 0; i < moves.size(); i++)
                    moves[i].first--;
 
                if (moves[0].first == 0)
                {
                    switch (dir)
                    {
                    case 0:
                        if (moves[0].second == 'D')
                            dir = 2;
                        else
                            dir = 3;
                        break;
                    case 1:
                        if (moves[0].second == 'D')
                            dir = 3;
                        else
                            dir = 2;
                        break;
                    case 2:
                        if (moves[0].second == 'D')
                            dir = 1;
                        else
                            dir = 0;
                        break;
                    case 3:
                        if (moves[0].second == 'D')
                            dir = 0;
                        else
                            dir = 1;
                        break;
                    }
                    moves.erase(moves.begin());
                }
            }
        }
        else
        {
            return;
        }
    }
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < k; i++)
    {
        int y, x;
        cin >> y >> x;
        map[y][x] = 2;
    }
    cin >> l;
    for (int i = 0; i < l; i++)
    {
        int a; char b;
        cin >> a >> b;
        moves.push_back({ a,b });
    }
    sort(moves.begin(), moves.end());
    bfs(1, 1);
    cout << ans + 1;
    return 0;
}
 cs

www.acmicpc.net/problem/3190

 

3190번: 뱀

 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[simulation, BOJ-14499] 주사위 굴리기, c+  (0) 2021.05.12
[mathmatics BOJ-13458] 시험감독, c++  (1) 2021.05.11
[Simulation, BOJ-12100] 2048(Easy), c++  (0) 2021.05.10
[graph theory, BOJ-13460] 구슬 탈출2, c++  (0) 2021.05.09
[graph theory, BOJ-1197] 최소 스패닝 트리, c++  (0) 2021.05.06

+ Recent posts

티스토리툴바