CodeDrive

문제:

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

(3) 3번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

(4) 4번 마을에 도착하면

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력:

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

출력:

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

풀이방법:

입력으로 들어오는 값들을 적절히 잘 정렬하는 것이 중요하다. 입력들을 시작하는 마을로 정렬하게 된다면 다음과 같은 문제가 발생할 수 있다.

C = 20

1 4 30

2 3 20

3 4 20

 이 경우에는 1번 마을에서 택배를 싣고 출발하지만, 중간의 마을에서는 택배를 싣지 못하게 된다. 하지만 이 케이스의 정답은 1번 마을에서는 택배를 적재하지 않고, 2번마을, 3번 마을에서 각각 20씩 싣는 것이 최대 박스 수를 얻을 수 있다. 

 따라서 시작하는 마을을 기준으로 정렬하는 것이 아닌 도착하는 마을을 기준으로 정렬을 하도록 한다. 그리고 각 마을마다 가능한 용량 C를 초기화하고, 한 박스를 적재할 때마다 감소시키며, 최대한 많은 박스를 싣도록 한다.

문제링크:

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

문제:

바퀴와 벨트를 이용하여 실험을 할 수 있는 과학 교구가 있다. 이 교구에는 다양한 종류의 바퀴와 벨트, 그리고 여러 개의 바퀴를 서로 다른 곳에 꽂을 수 있는 교구판이 포함되어 있다.

교구판에는 바퀴를 꽂을 수 있는 축들이 한 줄로 늘어서 있다. 모든 축에 바퀴를 꽂았을 때 바퀴끼리 부딪치지 않도록 축과 축 사이는 충분히 멀리 떨어져 있다. 각 축에는 바퀴가 하나씩 꽂혀있다. 바퀴는 왼쪽부터 순서대로 1번부터 차례대로 번호가 매겨져 있다. 

교구판에서 바로 옆에 있는 두 개의 바퀴는 항상 하나의 벨트로 연결해야 하는데, 이때 벨트를 0자 형태로 연결할 수도 있고 8자 형태로 한번 꼬아서 연결할 수도 있다. 그리고 한쪽 바퀴가 회전하게 되면 벨트로 연결된 다른 바퀴도 회전하게 되는데 이때 두 바퀴의 크기의 차이에 따라 두 바퀴의 회전수가 서로 다를 수 있다. 

다음 예는 3개의 벨트와 4개의 바퀴에 대한 정보가 주어진 경우이다. 이때 벨트 형태는 0자 형태(안꼬인 형태)면 0으로, 8자 형태(꼬인 형태)면 1로 나타낸다.

이 경우, 벨트 1은 바퀴 1과 바퀴 2를 0자 형태로 연결하며 바퀴 1이 1번 회전하는 동안 바퀴 2는 2번 회전하게 된다. 즉, 바퀴 1을 시계 방향으로 1회전시키면 바퀴 2는 시계 방향으로 2회전하게 된다. 

벨트 2는 바퀴 2와 바퀴 3을 꼬인 형태로 연결하며 바퀴 2가 1번 회전하는 동안 바퀴 3은 5번 회전하게 되므로, 바퀴 2를 시계 방향으로 1회전시키면 바퀴 3은 반시계 방향으로 5회전하게 된다. 

벨트 3은 바퀴 3과 바퀴 4를 0자 형태로 연결하며 바퀴 3이 2번 회전하는 동안 바퀴 4는 1번 회전하게 되므로, 바퀴 3을 시계 방향으로 2회전시키면 바퀴 4는 시계 방향으로 1회전하게 된다. 

따라서, 처음에 바퀴 1을 시계방향으로 1회전시키면 바퀴 2와 바퀴 3을 거쳐 결국 바퀴 4는 반시계방향으로 5회전하게 된다. 

벨트로 연결된 바퀴들의 회전수의 비와 벨트의 형태가 순서대로 주어졌을 때, 첫 번째 바퀴가 시계 방향으로 분당 1회전을 하는 경우 마지막 바퀴의 회전방향과 분당 회전수를 출력하는 프로그램을 작성하시오.

입력:

첫 줄에는 벨트의 개수를 나타내는 자연수 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 M개의 줄에는 1번 벨트부터 순서대로 벨트로 이어진 두 바퀴의 회전수의 비를 나타내는 두 개의 양의 정수 a, b와 벨트의 형태 0 또는 1이 한 줄에 주어진다. 즉, i번 벨트의 경우, i번 벨트로 이어진 두 바퀴 i와 i+1에 대해 바퀴 i가 a번 회전하는 동안 바퀴 i+1이 b번 회전하고 i번 벨트의 형태가 s(안꼬인 형태는 0, 꼬인 형태는 1)라면 a와 b, 그리고 s가 한 줄에 주어진다. 이때 모든 바퀴의 분당 회전수는 109 이하의 양의 정수로 결정되도록 입력이 주어진다. a, b는 109 이하의 양의 정수이고, a와 b는 서로소이다.

출력:

M+1번 바퀴의 회전 방향(시계방향은 0, 반시계방향은 1)과 분당 회전수를 한줄에 출력한다. 

풀이방법:

 순차적으로 벨트를 이동하며 회전수를 구하면 된다. 회전방향과 같은 경우에는 1이 들어온 경우에만 바뀌므로 나머지 연산을 통해 방향을 바꾼다.

 회전수를 구하는 방법은 b/a를 곱하는 것인데, 이 때, ans*=(b/a)와 같이 하면 에러가 발생하게 된다. 따라서 ans = (ans*b)/a와 같은 방법으로 회전 수를 구하도록 한다.

문제링크:

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

문제:

아래 mystery.c는 입력파일 X를 읽어서 그 안에 기록된 N개의 정수를 배열 NUM에 저장한 뒤에 이 N개의 수를 어떤 순서에 따라서 화면에 출력하는 프로그램이다. mystery.c가 X를 입력으로 받아 화면에 출력한 결과를 Y라고 하자.

#include <stdio.h>
int NUM[101] ;
FILE *fin ;
int main(){
    int i, token,N ;
    int count=0, from= 0, value ;
    fin = fopen("X","r");
    fscanf(fin,"%d",&N);
    for(i=0; i<N; i++){
        fscanf(fin,"%d",&token);
        NUM[i]= token;
    } /* end of for */
    printf("%d\n", N ) ;
    value = NUM[ from ] ;
    while( count < N ) {
        while( value == 0 ) { 
            from = (from+1)%N; 
            value = NUM[ from ] ; 
        } /* end of inner while */ 
        printf("%d ", value ) ;
        count++ ;
        NUM[ from ] = 0 ; 
        from = (value +from )% N ; 
        value = NUM[ from ] ; 
    } /* end of outer while */
    return(0);
} /* end of main() */

여러분은 mystery.c에서 생성된 Y를 파일로 받아서 그것의 입력에 해당하는 X를 찾아내는 프로그램을 작성해야 한다. 

입력:

첫 줄에는 정수 N (1 ≤ N ≤ 30)이 주어진다. 그리고 두 번째 줄에는 100이하 양의 정수 N개가 빈칸을 사이에 두고 모두 나열되어 있다. 단 그 정수 중에는 같은 수가 있을 수도 있다.

출력:

첫 줄에는 정수 N이 제시되어 있고, 그 다음 줄에는 N개의 양의 정수가 빈칸을 사이에 두고 기록되어 있어야 한다. 만일 입력을 생성하는 mystery.c의 입력파일 X가 없는 경우에는 음수인 -1 을 첫 줄에 출력하면 된다.

풀이방법:

주어진 코드를 역추적할 수 있도록 구현해야 하는 문제다. X가 없는 경우는 없기 때문에 -1은 고려하지 않아도 된다.

문제링크:

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

문제:

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.

1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
2. 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번 부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번 부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호속에 있는 숫자는 객차 번호를 나타낸다.

(1)(2)(3)(4)(5)(6)(7)

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님을 운송할 수 없다.

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다. 셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

출력:

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다.

풀이방법:

점화식을 생성해서 DP로 해당 문제를 풀 수 있다. DP는 다음과 같이 정의한다.

• DP[N][M]: 소형기관차 N대를 운행할 때 M번째 객차를 선택했을 때 최대로 운송 가능한 손님 수

따라서 점화식은 다음과 같다.

DP[N][M] = max( DP[N][M-1], DP[N-1][M-limit] + sum(numbers[M-limit+1:M+1]))

점화식을 사용해서 문제의 예제에 대입하면 다음과 같이 DP 테이블을 채워나갈 수 있다.

예시를 참고하여 어떠한 원리로 동작하는지 알아보도록 한다.

• DP[1][2] = max(DP[1][1], DP[0][2-2] + sum(numbers[2-2+1:2+1]))
  • DP[1][1], DP[0][0]는 둘 다 0이기때문에, sum만 계산하면 되므로 35+45다.
• DP[3][6] = max(DP[3][5], DP[2][6-2] + sum(numbers[6-2+1:6+1])
  • DP[3][5]는 0이므로, 뒷 항에 의해 결된다. DP[2][6-2]는 75+60이고, 여기에 30+45를 더해준다.

점화식이 의미하는 것은 현재 운행하고 있는 소형 기관차가 이전의 객차를 변경없이 유지했을 때(DP(N][M-1]), N번째 소형 기관차를 객차를 선택하기 전에 N-1번째 소형기관차를 유지하면서(DP[N-1][M-limit]) N번째 소형기관차가 M번째 소형기관차를 선택했을 때(sum(numbers[M-limit+1:M+1]))를 비교하는 것이다.

문제링크:

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

문제:

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

출력:

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

풀이방법:

 겹치지 않도록 최대한 많이 선택해야 하는 문제다. 이는 곧 가장 긴 증가하는 부분 수열(LIS) 문제와 같다. 따라서 LIS 알고리즘을 사용하여 가장 긴 증가하는 부분 수열을 찾으면서 그 부분 수열의 번호들도 같이 찾는 문제에 해당한다.

 LIS 문제를 해결하는 방법에는 여러가지가 있지만, 이 문제에서는 bisect를 이용했다. 이 방법의 핵심은 최대한 작은 수들을 고르는 것이 가장 긴 증가하는 부분 수열을 만들기 유리하다는 것이다. 1 2 7 이라는 부분 수열과 1 2 4 이라는 부분 수열이 있을 때 후자의 경우가 더 긴 부분 수열을 만들 확률이 높다는 것이다. 따라서 입력으로 들어오는 배열에서 bisect을 이용하여 계속해서 배열을 최신화한다.

하지만 이 때 만드는 배열은 실제 가장 긴 증가하는 부분 수열은 아니다. 이는 길이만을 알 수 있기 때문에, 만드는 동시에 위치 정보도 같이 추가하여 마지막에 실제 가장 긴 부분수열을 찾을 수 있도록 한다. 이 때 사용하는 것이 idx 배열이며 , start의 각 원소가 몇 번째 자리에 들어가는지에 대한 여부다. idx=[0,0,1,1,2]라는 것은 2가 0번째, 4가 0번째, 1이 1번째, 5가 1번째, 3이 2번째 자리에 각각 들어가게 된다는 것이다. 따라서 역순으로 idx 배열을 탐색하면서 2, 1, 0이 먼저 나오는 순서로 넣는 것이 최종 답에 해당한다. (나중에 들어간 것이 마지막에 남아 있는 수들이기 때문)

문제링크:

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

문제:

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

그림 1

출력:

첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

풀이방법:

 주사위는 상하로 연결되어 있기 때문에, 이를 위한 새로운 인덱스가 필요하다. 따라서 각 인덱스별로 연관있는 면의 인덱스를 담고 있는 dict을 만들도록 한다.

 그리고 첫 밑면에 따라 모든 경우의 수를 고려할 수 있도록 구현하도록 한다. 1번 주사위에 따라 2번부터 주사위가 결정되기 때문이다. 밑면의 숫자를 고르면 자동으로 윗 숫자가 결정되게 되고, 옆면의 숫자는 회전이 가능하기 때문에 남은 숫자 중에 max 값을 고른다.

 그 뒤로는 첫 주사위의 윗면의 숫자로 다음 주사위의 아래 인덱스가 결정되기 때문에 주사위는 순차적으로 주사위를 올리면서 옆면 중  max 값을 찾으면 된다.

문제링크:

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

문제:

오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다.

그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자.

위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반이었던 사람은 2번 학생, 3번 학생과 5번 학생으로 모두 3명이다. 이 예에서 4번 학생이 전체 학생 중에서 같은 반이었던 학생 수가 제일 많으므로 임시 반장이 된다.

각 학생들이 1학년부터 5학년까지 속했던 반이 주어질 때, 임시 반장을 정하는 프로그램을 작성하시오.

입력:

첫째 줄에는 반의 학생 수를 나타내는 정수가 주어진다. 학생 수는 3 이상 1000 이하이다. 둘째 줄부터는 1번 학생부터 차례대로 각 줄마다 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 5개의 정수가 빈칸 하나를 사이에 두고 주어진다. 주어지는 정수는 모두 1 이상 9 이하의 정수이다.

출력:

첫 줄에 임시 반장으로 정해진 학생의 번호를 출력한다. 단, 임시 반장이 될 수 있는 학생이 여러 명인 경우에는 그 중 가장 작은 번호만 출력한다.

풀이방법:

 학생들간의 정보를 가지고 있는 Nx N 행렬을 만들도록 한다. 그리고 선생님이 만든 각 학생들이 몇 반에 속했었는지를 나타낸 표를 통해 학생들간의 같은 반 유무를 행렬에 담도록 한다. 같은 반이 된 적이 있다면 1로 표기를 하며 넘어가도록 한다. 이 때, 양 방향으로 카운트를 올려주도록 한다. (1번, 3번이 같은 반이 된 적이 있다면 1번, 3번 둘 다 카운트를 올려줘야 한다.)

문제링크:

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

문제:

0부터 9까지의 숫자가 표시된 카드를 가지고 두 사람 A와 B가 게임을 한다. A와 B에게는 각각 0에서 9까지의 숫자가 하나씩 표시된 10장의 카드뭉치가 주어진다. 두 사람은 카드를 임의의 순서로 섞은 후 숫자가 보이지 않게 일렬로 늘어  놓고 게임을 시작한다. 단, 게임 도중 카드의 순서를 바꿀 수는 없다.

A와 B 각각이 늘어놓은 카드를 뒤집어서 표시된 숫자를 확인하는 것을 한 라운드라고 한다. 게임은 첫 번째 놓인 카드부터 시작하여 순서대로 10번의 라운드로 진행된다. 각 라운드에서는 공개된 숫자가 더 큰 사람이 승자가 된다. 승자에게는 승점 3점이 주어지고 패자에게는 승점이 주어지지 않는다. 만약 공개된 두 숫자가 같아서 비기게 되면, A, B 모두에게 승점 1점이 주어진다. 

10번의 라운드가 모두 진행된 후, 총 승점이 큰 사람이 게임의 승자가 된다. 만약, A와 B의 총 승점이 같은 경우에는, 제일 마지막에 이긴 사람을 게임의 승자로 정한다. 그래도 승부가 나지 않는 경우는 모든 라운드에서 비기는 경우뿐이고 이 경우에 두 사람은 비겼다고 한다.

예를 들어, 다음 표에서 3번째 줄은 각 라운드의 승자를 표시하고 있다. 표에서 D는 무승부를 나타낸다. 이 경우에 A의 총 승점은 16점이고, B는 13점이어서, A가 게임의 승자가 된다. 

아래 표의 경우에는 A와 B의 총 승점은 13점으로 같다. 마지막으로 승부가 난 라운드는 7번째 라운드이고, 이 라운드의 승자인 B가 게임의 승자가 된다. 

A와 B가 늘어놓은 카드의 숫자가 순서대로 주어질 때, 게임의 승자가 A인지 B인지, 또는 비겼는지 결정하는 프로그램을 작성하시오.

입력:

입력 파일은 두 개의 줄로 이루어진다. 첫 번째 줄에는 A가 늘어놓은 카드의 숫자들이 빈칸을 사이에 두고 순서대로 주어진다. 두 번째 줄에는 B가 늘어놓은 카드의 숫자들이 빈칸을 사이에 두고 순서대로 주어진다. 

출력:

첫 번째 줄에는 게임이 끝난 후, A와 B가 받은 총 승점을 순서대로 빈칸을 사이에 두고 출력한다. 두 번째 줄에는 이긴 사람이 A인지 B인지 결정해서, 이긴 사람을 문자 A 또는 B로 출력한다. 만약 비기는 경우에는 문자 D를 출력한다. 

풀이방법:

 각 라운드를 진행하면서 A의 점수, B의 점수를 더해주도록 한다. 이와 동시에 history라는 배열에 누가 이겼는지 혹은 비겼는지에 대해 기록하도록 한다.

 모든 라운드가 종료한 뒤로, 서로 점수가 다르다면 더 높은 사람을 출력하도록 하고, 점수가 같다면, history를 사용하여 제일 마지막으로 이긴 사람을 찾도록 한다.

문제링크:

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

문제:

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

입력:

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

출력:

첫째 줄에는 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 크기가 작은 수부터 하나의 공백을 사이에 두고 출력한다. 입력되는 두 자연수를 최대공약수와 최소공배수로 하는 두 개의 자연수 쌍이 여러 개 있는 경우에는 두 자연수의 합이 최소가 되는 두 수를 출력한다.

풀이방법:

 어떤 두 자연수를 A, B라고 하고, 최대공약수를 G,  최소공배수를 L이라고 하자. 최대공약수는 공통인 약수들 중에서 가장 큰 수이기 때문에 두 자연수 A, B는 A=aG, B=bG와 같이 표현할 수 있다. 그리고 최소공배수는 두 자연수의 공통인 배수들 중에서 가장 작은 수이므로 L=abG라고 표현할 수 있다. (aG와 bG의 공통의 배수이기 때문)

 따라서 최대공약수와 최소공배수 간의 관계는 ab= L/G라고 할 수 있다. A와 B를 찾기 위해 G는 이미 알고 있으므로 가능한 a와 b를 구하도록 한다. 즉, ab의 약수들을 찾으면 되는 문제다.

 ab의 약수들을 기반으로 A와 B 값을 구한 뒤에 문제의 조건처럼 두 자연수의 합이 최소가 되도록 정렬을 수행하여 두 수를 찾는다. 

문제링크:

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

문제:

체조나 다이빙 등의 경기에서 일부 심판이 자기가 좋아하는 선수에게 높은 점수를, 싫어하는 선수에게 낮은 점수를 주는 경우가 종종 있었다. 따라서 심판들이 주는 점수의 평균점수를 선수에게 주게 되면 공정하지 않은 경우가 생길 수 있다. 이를 방지하기 위하여 절사평균이나 보정평균을 사용한다. 예를 들어 심사위원 일곱 명이 다음과 같이 점수를 주었다고 하자.

9.3, 9.5, 9.6, 9.8, 9.1, 5.0, 9.3

전체의 합이 61.6이 되므로 평균은 8.8이 된다. 이 평균점수는 한 심판이 다른 심판에 비하여 아주 낮은 점수인 5.0을 주어서 나온 결과로, 선수는 매우 불공정하다고 느낄 것이다.

위의 점수를 작은데서 큰 순서로 정렬하면 5.0, 9.1, 9.3, 9.3, 9.5, 9.6, 9.8 이 된다.

이때 절사평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 두 개씩을 제외하고 난 9.3, 9.3, 9.5의 평균인 9.37이 된다(소수점이하 셋째 자리에서 반올림). 또 보정평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 각각 두 개를, 남은 점수 중 가장 가까운 것으로 교체한 9.3, 9.3, 9.3, 9.3, 9.5, 9.5, 9.5의 평균으로 9.39가 된다(소수점이하 셋째 자리에서 반올림).

N개의 점수와 양쪽에서 제외하는 개수 K 값이 주어졌을 때 절사평균(N, K)와 보정평균(N, K)를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에 전체 점수의 개수 N과 제외되는 점수의 개수 K가 빈칸을 사이에 두고 주어진다. N은 3 이상 100,000 이하의 자연수이다. K는 0 이상 (N/2)-1 이하로 주어진다. 그 다음 N줄에는 각 심판의 점수가 한 줄에 하나씩 주어진다. 점수는 0 이상 10 이하의 실수로 소수점이하 첫째 자리까지 주어진다.

출력:

첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우에는 5.50으로 출력한다.

풀이방법:

 조건에 맞게 필요하지 않은 값을 제외하고 평균을 구하면 되는 문제지만, 부동 소수점을 고려해야 한다. 부동 소수점 문제는 컴퓨터가 float을 표현할 때 발생하는 것을 의미한다. 예를 들어 0.3이 입력으로 들어와서 a라는 변수에 저장한다고 해도, a에는 정확히 0.3의 값이 들어가는 것이 아니라 0.3000000000001과 같이 부정확하게 값을 가지게 된다. 따라서 이러한 값들이 누적되어 평균을 구하게 되면 원래 원하던 평균과 달라지게 된다. 따라서 이러한 문제를 해결할 수 있는 여러 가지 방법이 있다.

 일반적으로 float을 지수 부분, 가수 부분으로 나눌 수 있기 때문에 이를 사용하는 방법이 있고, Python에서 이러한 문제점을 해결하기 위해 Decimal이라는 라이브러리를 제공하기도 한다. 하지만 1e-8과 같이 아주 작은 수를 더해주면 해결되는 방법도 있다고 한다. 따라서 평균을 구할 때, 1e-8과 같은 작은 수를 더해 부동소수점 문제를 해결하도록 한다.

문제링크:

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