[Algorithem] KOI 2014 지역본선 초등부

1번 과자

---

동수는 제과점에 과자를 사러 가는데 현재 가진 돈이 모자랄 경우 부모님께 모자란 돈을 받으려고 한다. 과자 한 개의 가격이 K, 사려고 하는 과자의 개수가 N이고, 현재 가진 돈의 액수를 M이라 할 때 여러분은 동수가 부모님께 받아야 하는 모자란 돈을 계산하려고 한다. 

예를 들어, 과자 한 개의 가격이 30원, 사려고 하는 과자의 개수가 4개, 현재 동수가 가진 돈이 100원이라 할 때, 동수가 부모님께 받아야 하는 돈은 20원이다. 과자 한 개의 가격이 250원, 사려고 하는 과자의 개수가 2개, 현재 동수가 가진 돈이 140원이라 할 때, 동수가 부모님께 받아야 하는 돈은 360원이다. 과자 한 개의 가격이 20원, 사려고 하는 과자의 개수가 6개, 현재 동수가 가진 돈이 120원이라 할 때 동수가 부모님께 받아야 하는 돈은 0원이다. 과자 한 개의 가격이 20원, 사려고 하는 과자의 개수가 10개, 현재 동수가 가진 돈이 320원이라 할 때 동수가 부모님께 받아야 하는 돈은 역시 0원이다. 

과자 한 개의 가격, 사려고 하는 과자의 개수와 동수가 현재 가진 돈의 액수가 주어질 때 동수가 부모님께 받아야 하는 돈의 액수를 출력하는 프로그램을 작성하시오. 

입력

첫 번째 줄에는 과자 한 개의 가격 K, 사려고 하는 과자의 개수 N, 현재 동수가 가진 돈 M이 각각 공백을 사이에 두고 주어진다. 단, K, N은 1,000 이하의 양의 정수이고, M은 10만 이하의 양의 정수이다. (1 ≤ K, N ≤ 1,000, 1 ≤ M ≤ 100,000이다.) 

출력

첫 줄에 동수가 부모님께 받아야 하는 돈의 액수를 출력한다. 

예제입력	예제출력
300 4 1000	200

풀이

고려해야할 경우는 2가지이다.

첫째, K × N > M인 경우 돈이 부족하여 부모님에게 돈을 K × N - M 만큼 받아야 된다.

둘째, 만약에 K × N ≦ M인 경우, 과자를 사기에 돈이 충분하여 돈을 받지 않아도 된다. 

#include <stdio.h>

int main()
{
    int K;    // 과자 한 개의 가격
    int N;    // 사려고 하는 과자의 개수
    int M;    // 현재 동수가 가진 돈

    scanf("%d %d %d", &K, &N, &M);
    
    // 삼항연산자
    (K * N) >= M ? printf("%d", K * N - M) : printf("0");

    return 0;
}

2번 자리배정

---

어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다. 

예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. 

이 공연장에 입장하기 위하여 많은 사람이 대기줄에 서있다. 기다리고 있는 사람들은 제일 앞에서부터 1, 2, 3, 4, . 순으로 대기번호표를 받았다. 우리는 대기번호를 가진 사람들에 대하여 (1,1)위치 좌석부터 시작하여 시계방향으로 돌아가면서 비어있는 좌석에 관객을 순서대로 배정한다. 이것을 좀 더 구체적으로 설명하면 다음과 같다.

먼저 첫 번째 사람, 즉 대기번호 1인 사람은 자리 (1,1)에 배정한다. 그 다음에는 위쪽 방향의 좌석으로 올라가면서 다음 사람들을 배정한다. 만일 더 이상 위쪽 방향으로 빈 좌석이 없으면 오른쪽으로 가면서 배정한다. 오른쪽에 더 이상 빈자리가 없으면 아래쪽으로 내려간다. 그리고 아래쪽에 더 이상 자리가 없으면 왼쪽으로 가면서 남은 빈 좌석을 배정한다. 이 후 왼쪽으로 더 이상의 빈 좌석이 없으면 다시 위쪽으로 배정하고, 이 과정을 모든 좌석이 배정될 때까지 반복한다. 

아래 그림은 7×6공연장에서 대기번호 1번부터 42번까지의 관객이 좌석에 배정된 결과를 보여주고 있다.

여러분은 공연장의 크기를 나타내는 자연수 C와 R이 주어져 있을 때, 대기 순서가 K인 관객에게 배정될 좌석 번호 (x,y)를 찾는 프로그램을 작성해야 한다.

입력

첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. 단 1 ≤ K ≤ 100,000,000이다.

출력

입력으로 제시된 대기번호 K인 관객에게 배정될 좌석번호 (x,y)를 구해서 두 값, x와 y를 하나의 공백을 사이에 두고 출력해야 한다. 만일 모든 좌석이 배정되어 해당 대기번호의 관객에게 좌석을 배정할 수 없는 경우에는 0(숫자 영)을 출력해야 한다. 

예제입력	예제출력
7 6  11	6 6

풀이

대기 번호는 (1,1)에서 시작하여 (1,2), (1,3), (1,4), (1,5) ,.... 순으로 증가하다가 (1,R)에서 방 향을 바꿔 (2,R) , (3,R) ... 순으로 나아가게 된다. 이렇게 대기번호를 한 단계씩 늘려가면서 시뮬레이션을 통해 대기번호에 따른 좌표를 구하는 방법이다.

#include <stdio.h>
#define N 1024
int arr[N][N];

int main()
{
    int p = 0, q = 0;   // p = y의 좌표, q는 x의 좌표
    int C, R, K, count = 1;   // C = 가로, R = 세로, K = 대기번호
    scanf("%d %d %d", &C, &R, &K);
    
    // 관객에게 좌석을 배정할 수 없는 경우
    if(C * R < K)
    {
        printf("0");
        return 0;
    }
    
    arr[p][q] = count++;
    while(count <= C * R && K + 1 != count)
    {
        while(arr[p][q+1] == 0 && q + 1 < R && K + 1 != count) arr[p][++q]=count++;    // 오른방향
        while(arr[p+1][q] == 0 && p + 1 < C && K + 1 != count) arr[++p][q]=count++;    // 아랫방향
        while(arr[p][q-1] == 0 && q > 0 && K + 1 != count) arr[p][--q]=count++;    // 왼쪽방향
        while(arr[p-1][q] == 0 && p > 0 && K + 1 != count) arr[--p][q]=count++;    // 윗방향
    }
    printf("%d %d", p + 1, q + 1);
    return 0;
}

3번 개미

---

가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다. 

여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다. 

문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다. 

입력

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다.

출력

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다. 

예제입력	예제출력
6 4  4 1  8	0 1

풀이

그림을 보고 x좌표와 y좌표가 서로 독립적인 것을 눈치채지 못하는 함정에 빠질 수 있다.

서로 독집적인 x좌표와 y좌표는 따로 계산을 할 수 있다.

개미의 최종적인 x좌표를 구하는 방법은 다음과 같다.

개미가 격자 공간에서 x좌표의 경계(x = 0 or x = w)에 닿는 횟수를 계산한다. cx를 그 횟수라고 할 때 값은 cx = (p + t) / w 이며, t 시간이 지난 뒤 개미의 최종 x 좌표는 아래와 같다.

cx가 짝수일 때: w - ((p +t) % w)

cx가 홀수일 때: ((p +t) % w)

마찬가지의 방법으로 t 시간이 지난 뒤 개미의 최종 y 좌표를 구할 수 있다. 

#include <stdio.h>

int main()
{
    int w, h;    // w = 가로의 길이, h = 세로의 길이
    int p ,q, t;    // p = 초기 x의 좌표값, q = 초기 y의 좌표값, t = 개미가 움직일 시간
    int cx, cy;    // cx = x좌표의 경계에 닿는 횟수, cy = y좌표의 경계에 닿는 횟수
    scanf("%d %d", &w ,&h);
    scanf("%d %d", &p, &q);
    scanf("%d", &t);
    
    cx = (p + t) / w;    // x좌표의 경계에 닿는 횟수
    cy = (q + t) / h;    // y좌표의 경계에 닿는 횟수
    
    if(cx % 2 == 0)
        p = (p + t) % w;    // cx가 짝수일 때, 횟수 계산
    else
        p = w - ((p + t) % w);    // cx가 홀수일 때, 횟수 계산
    
    if(cy % 2 == 0)
        q = (q + t) % h;    // cy가 짝수일 때, 횟수 계산
    else
        q = h - ((q + t) % h);    // cy가 짝수일 때, 횟수 계산
    
    printf("%d %d", p, q);
    return 0;
}

4번 저울

---

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)

[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다. 

비교 결과가 모순되는 입력은 없다고 가정한다. 위 예제의 기존 측정 결과에 [3]>[1]이 추가되었다고 가정하자. 이 경우 [1]>[2], [2]>[3]이므로 우리는 [1]>[3]이라는 것을 예측할 수 있는데, 이는 기존에 측정된 결과 [3]>[1]과 서로 모순이므로 이러한 입력은 가능하지 않다. 

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하는 프로그램을 작성하시오. 

입력

첫 줄에는 물건의 개수 N이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

예제입력	예제출력
6  5  1 2  2 3  3 4  5 4  6 5	2  2  2  0  3  3

풀이

그래프로 그려서 문제를 풀면 쉽게 풀릴 수 있다. N 개의 물건은 노드로 표현하고, 각 물건 무게 사이의 관계는 단방향 간선으로 표현을 한다.

[x] > [y]와 같은 입력이 주어졌을 때, 이것을 x 노드에서 y 노드로 가는 단방향 간선으로 표현한다. 이런 방법으로 입력 받은 물건들의 무게 관계를 그래프로 표현하고, DFS나 BFS 알고리즘을 사용하여 답을 구할 수 있다.

#include <stdio.h>
#define Num 128
int arr[Num][Num];

int main()
{
    int N, M;    // N = 물건의 개수, M = 물건 쌍의 개수
    scanf("%d %d", &N, &M);
    
    // 그래프를 인접행렬로 표현한다.
    for(int i = 1, x, y; i <= M; i++)
    {
        scanf("%d %d", &x, &y);
        arr[x][y] = 1;
    }
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(arr[j][i])
            {
                for(int k = 1; k <= N; k++)
                    if(arr[i][k]) arr[j][k] = 1;
            }
        }
    }
    
    for (int i = 1; i <= N; i++)
    {
        int count = 0;
        for (int j = 1; j <= N; j++) 
            if (i != j && arr[i][j] + arr[j][i] == 0)
                count++;
        printf ("%d\n",count);
    }
    
    return 0;
}

공부를 하며 문제를 푸는지라 시간이 상당히 걸렸습니다. 도움을 주신 YJH님 감사합니다.

 

※ 문제 출처: 한국 정보 올림피아드, BOJ