띠그랭

맥주 마시면서 걸어가기 9205번

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

기본적인 BFS()문제인데 맨허튼 거리라서 좀 쉽게 풀린 거같다. 만약 유클리드 거리 방식으로 문제를 풀었다고 하면 식만 좀더 변형하면 될거같다.

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다.

예제 입력 1

 
xxxxxxxxxx
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000

예제 출력 1

 
happy
sad

소스 코드

 
​x
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
​
int t;  // 테스트케이스 수
int n;  // 편의점 갯수
int me_y, me_x;     // 상근이네 집 좌표
vector<pair<int, int>> cu;  // 편이점 좌표
int lock_y, lock_x;     // 락 페스티벌 좌표
int res;
​
void BFS()
{
    queue<pair<int, int>> q;
    q.push({ me_y,me_x });
    int chk[100] = {0}; // 편의점 체크용
    res = 0;
    while (1)
    {
        if (q.empty() || res == 1) break;
        int here_y = q.front().first;
        int here_x = q.front().second;
        q.pop();
​
        for (int i = 0; i < cu.size(); i++)
        {
            if (abs(here_y - cu[i].first) + abs(here_x - cu[i].second) <= 1000 && chk[i] == 0)  // 편의점에 도달 할 수 있을 때
            {
                q.push({ cu[i].first , cu[i].second });
                chk[i] = 1;
            }
            else if (abs(here_y - lock_y) + abs(here_x - lock_x) <= 1000)   // 현재 위치에서 락 페스티벌 까지 도달 할 수 있을 경우
                res = 1;
        }
    }
}
​
void input()
{
    cin >> t;
    for (int k = 0; k < t; k++)
    {
        cu.clear();
        cin >> n;
        cin >> me_y >> me_x;
        for (int i = 0; i < n; i++)
        {
            int y, x;
            cin >> y >> x;
            cu.push_back({ y,x });
        }
        cin >> lock_y >> lock_x;
        BFS();
        if (res == 1) cout << "happy" << '\n';
        else cout << "sad" << '\n';
    }
}
​
int main()
{
    input();
​
    return 0;
}

경비원 2564번

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

15:26 시작 —> 16:10 종료

단순 구현문제인데, 상점과 동근이의 위치를 y좌표 , x좌표를 똭 준게 아니라, (동-4,서-3,남-2,북-1) 요로코롬 주어서 데이터 입력시 좀 변형을 주어 값을 저장 했다.

예를 들어서 동근이의 좌표를 2 3 을 주었다고 한다면 , 2는 남쪽을 뜻하며, 3은 서쪽으로부터 떨어진 거리를 의미한다. 그래서 저장할 때는 y좌표를 map의 세로 최대 크기M을 저장했고, x좌표는 그대로 3을 저장했다. 그래서 최종적으로 동근이의 위치는 (M, 3) 여기서 M = 5를 의미한다.(예제 기준)

이렇게 동 서 남 북 4가지의 저장 방식을 달리 하니, 동근이의 위치와 상점의 위치의 최단 거리를 구할 때 소스코드 자체가 많이 간결해 졌다(흠 그래도 입력받을때나, 소스 자체가 더러운건 실력이 부족한거같다). 이 의미는 아마 풀어보면 느낌 적인 느낌이 올것이다.

문제

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 불록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

출력

첫째 줄에 동근이의 위치와 각 상점 사이의 최단 거리의 합을 출력한다.

예제 입력 1

 
xxxxxxxxxx
10 5
3
1 4
3 2
2 8
2 3

예제 출력 1

 
23

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
int N, M;   // N : 가로 , M : 세로
int k;  // k : 상점의 갯수
vector<pair<int, int>> v;
int my_y, my_x;     // 동근이 위치
int res;
​
void input()
{
    cin >> N >> M;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        int dir, tmp;
        int y, x;
        cin >> dir >> tmp;
        if (dir == 1)
        {
            y = 0;
            x = tmp;
        }
        else if (dir == 2)
        {
            y = M;
            x = tmp;
        }
        else if (dir == 3)
        {
            y = tmp;
            x = 0;
        }
        else if (dir == 4)
        {
            y = tmp;
            x = N;
        }
        v.push_back({ y, x });
    }
    int me_dir, me_d;
    cin >> me_dir >> me_d;
    if (me_dir == 1)
    {
        my_y = 0;
        my_x = me_d;
    }
    else if (me_dir == 2)
    {
        my_y = M;
        my_x = me_d;
    }
    else if (me_dir == 3)
    {
        my_y = me_d;
        my_x = 0;
    }
    else if (me_dir == 4)
    {
        my_y = me_d;
        my_x = N;
    }
}
​
void engine()
{
    for (int i = 0; i < v.size(); i++)
    {
        if (my_y == v[i].first)     // 같은 방향 일때
            res += abs(my_x - v[i].second);
​
        else if (my_y == 0) //  동근이가 북쪽일 때
        {
            if (v[i].first == M)        // 상점이 반대편(남) 일때
            {
                int tmp;
                tmp = min(my_x + v[i].second, (N - my_x) + (N - v[i].second));
                res += tmp + M;
            }
            else  // 옆쪽 일 때
            {
                int tmp = abs(my_y - v[i].first) + abs(my_x - v[i].second);
                res += tmp;
            }
        }
​
        else if (my_y == M) // 동근이가 남쪽일 때
        {
            if (v[i].first == 0)        // 상점이 반대편(북) 일때
            {
                int tmp;
                tmp = min(my_x + v[i].second, (N - my_x) + (N - v[i].second));
                res += tmp + M;
            }
            else  // 옆쪽 일 때
            {
                int tmp = abs(my_y - v[i].first) + abs(my_x - v[i].second);
                res += tmp;
            }
        }
        else if (my_x == 0) // 동근이가 서쪽일 때
        {
            if (v[i].second == N)   // 상점이 반대편(동) 일때
            {
                int tmp;
                tmp = min(my_y + v[i].first , (M - my_y) + (M - v[i].first));
                res += tmp + N;
            }
            else  // 옆쪽 일 때
            {
                int tmp = abs(my_y - v[i].first) + abs(my_x - v[i].second);
                res += tmp;
            }
        }
        else if (my_x == N)     // 동근이가 동쪽일 때
        {
            if (v[i].second == 0)   // 상점이 반대편(서) 일때
            {
                int tmp;
                tmp = min(my_y + v[i].first, (M - my_y) + (M - v[i].first));
                res += tmp + N;
            }
            else // 옆쪽 일 때
            {
                int tmp = abs(my_y - v[i].first) + abs(my_x - v[i].second);
                res += tmp;
            }
        }
    }
}
​
int main()
{
    input();
​
    engine();
​
    cout << res << '\n';
​
    return 0;
}

삼성 코딩 테스트 기출 - 시험 감독 13458번

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

12:11 시작 —> 12:32 종료

단순 구현문제라 최대한 빨리 푸는게 중요한 문제 같다.

감독관의 수가 int형을 넘어갈 수 있어 long long을 써야 한다는 거 말고는 그다지 함정은 없는거 같음.

문제

총 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)

출력

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

예제 입력 1

 
xxxxxxxxxx
1
1
1 1

예제 출력 1

 
xxxxxxxxxx
1

예제 입력 2

 
xxxxxxxxxx
3
3 4 5
2 2

예제 출력 2

 
xxxxxxxxxx
7

예제 입력 3

 
xxxxxxxxxx
5
1000000 1000000 1000000 1000000 1000000
5 7

예제 출력 3

 
xxxxxxxxxx
714290

예제 입력 4

 
xxxxxxxxxx
5
10 9 10 9 10
7 20

예제 출력 4

 
xxxxxxxxxx
10

예제 입력 5

 
xxxxxxxxxx
5
10 9 10 9 10
7 2

예제 출력 5

 
13

소스 코드

 
xxxxxxxxxx
#include<iostream>
​
using namespace std;
​
int N; // 시험장의 갯수
int A[1000001]; // 각 시험장 응시자 수
int B, C;   // B : 총감독관이 감시할 수 있는 수 , C : 부감독관이 감시 할 수 있는 수
long long res;  // 감독관 최소 수
​
void input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    cin >> B >> C;
}
​
void engine()
{
    for (int i = 1; i <= N; i++)
    {
        int tmp = A[i] - B;
        if (tmp <= 0)   // 감독관 1명만 필요할 때
            res += 1;
        else    // 부감독관도 필요할 때
        {
            if (tmp % C == 0)
                res += (tmp / C) + 1;
            else
                res += (tmp / C) + 2;
        }
    }
}
​
int main()
{
​
    input();    // 입력 받기
​
    engine();
​
    cout << res << '\n';
​
    return 0;
}