출처: [백준] 20301번 반전 요세푸스

문제

요세푸스 문제는 다음과 같다.

1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K(≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N, K, M)–반전 요세푸스 순열이라고 하며, (7, 3, 4)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩가 된다.

N, K, M이 주어질 때, (N, K, M)–반전 요세푸스 순열을 계산해 보자.

입력

첫째 줄에 정수 N, K, M이 주어진다. (1≤N≤5 000, 1≤K,M≤N)

출력

(N, K, M)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

1

7 3 4

예제 출력 1

1
2
3
4
5
6
7

3
6
2
7
1
5
4

출처

• University > 서강대학교 > 2020 Sogang Programming Contest (Master) C번
  • 문제를 검수한 사람: gumgood, jhnah917, pichulia, QuqqU, rhs0266, shiftpsh, sogangcse, woonikim
  • 문제를 만든 사람: sbrus_1213

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱

소스코드 (최초)

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

import sys
from collections import deque

input = sys.stdin.readline

N, K, M = map(int, input().split())

people = deque(x for x in range(1, N + 1))

count = 0
direction = 1
while people:
    if direction:  # 오른쪽
        for _ in range(K - 1):
            people.append(people[0])
            people.popleft()
    elif not direction:  # 왼쪽
        for _ in range(K):
            people.appendleft(people.pop())

    print(people.popleft())
    count += 1
    if count == M:
        count = 0
        direction = not direction

소스코드 (수정)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import sys
from collections import deque

input = sys.stdin.readline

N, K, M = map(int, input().split())

people = deque(x for x in range(1, N + 1))

while people:
    for _ in range(M):
        people.rotate(-(K - 1))  # 오른쪽
        if not people:
            break
        print(people.popleft())

    for _ in range(M):
        people.rotate(K)  # 왼쪽
        if not people:
            break
        print(people.popleft())

출처: [백준] 5464번 주차장

문제

시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영된다. 차가 주차장에 도착하면, 주차장 관리인이 비어있는 주차 공간이 있는지를 검사한다. 만일 비어있는 공간이 없으면, 차량을 빈 공간이 생길 때까지 입구에서 기다리게 한다. 만일 빈 주차 공간이 하나만 있거나 또는 빈 주차 공간이 없다가 한 대의 차량이 주차장을 떠나면 곧바로 그 장소에 주차를 하게 한다. 만일 빈 주차 공간이 여러 곳이 있으면, 그 중 번호가 가장 작은 주차 공간에 주차하도록 한다. 만일 주차장에 여러 대의 차량이 도착하면, 일단 도착한 순서대로 입구의 대기장소에서 줄을 서서 기다려야 한다. 대기장소는 큐(queue)와 같이, 먼저 대기한 차량부터 주차한다.

주차료는 주차한 시간이 아닌 차량의 무게에 비례하는 방식으로 책정된다. 주차료는 차랑의 무게에다 주차 공간마다 따로 책정된 단위 무게당 요금을 곱한 가격이다.

주차장 관리원은 오늘 M대의 차량이 주차장을 이용할 것이라는 것을 알고 있다. 또한, 차량들이 들어오고 나가는 순서도 알고 있다.

주차 공간별 요금과 차량들의 무게와 출입 순서가 주어질 때, 오늘 하룻동안 주차장이 벌어들일 총 수입을 계산하는 프로그램을 작성하라.

입력

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다.

• 첫 번째 줄에는 정수 N과 M이 빈칸을 사이에 두고 주어진다.

• 그 다음 N개의 줄에는 주차 공간들의 단위 무게당 요금을 나타내는 정수들이 주어진다. 그 중 s번째 줄에는 주차 공간 s의 단위 무게당 요금 Rs가 들어있다.

• 그 다음 M개의 줄에는 차량들의 무게를 나타내는 정수들이 주어진다. 차량들은 1 부터 M 까지 번호로 구분되고, 이 번호는 출입 순서와는 상관없다. 이 M개의 줄 중 k번째 줄에는 차량 k의 무게를 나타내는 정수 Wk가 들어있다.

• 그 다음 2*M 개의 줄에는 차량들의 주차장 출입 순서를 나타내는 정수들이 한 줄에 하나씩 주어진다. 양의 정수 i는 차량 i가 주차장에 들어오는 것을 의미하고, 음의 정수 -i는 차량 i가 주차장에서 나가는 것을 의미한다. 주차장에 들어오지 않은 차량이 주차장에서 나가는 경우는 없다. 1 번부터 M 번까지 모든 차량은 정확하게 한 번씩 주차장에 들어오고, 한 번씩 주차장에서 나간다. 또한 입구에서 대기 중인 차량이 주차를 하지 못하고 나가는 경우는 없다.

• 1 ≤ N ≤ 100 주차 공간의 수

• 1 ≤ M ≤ 2,000 차량의 수

• 1 ≤ Rs ≤ 100 주차 공간 s의 단위 무게당 요금

• 1 ≤ Wk ≤ 10,000 차량 k의 무게

출력

출력은 반드시 표준 출력으로 하여야 하며, 하나의 줄에 한 개의 정수를 출력한다. 이 정수는 오늘 하룻동안 주차장이 벌어들인 총 수입이다.

예제 입력 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

예제 출력 1

1

5300

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

예제 출력 2

1

16200

힌트

• 차량 3이 주차 공간 1에 주차한다. 주차료는 300 * 2 = 600 이다.
• 차량 2가 주차 공간 2에 주차한다. 주차료는 100 * 3 = 300 이다.
• 차량 1이 차랑 3이 떠난 주차공간 1에 주차한다. 주차료는 200 * 2 = 400 이다.
• 차량 4가 마지막 남은 주차 공간 3에 주차한다. 주차료는 800 * 5 = 4,000 이다.

출처

• Olympiad > International Olympiad in Informatics > IOI 2009 5번

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 큐

소스코드

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

import sys
from collections import deque
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
# N~: 단위 무게당 요금을 나타내는 정수, N: 주차공간 1,2,3....
# M~: 차량들의 무게


fees = [int(input()) for _ in range(N)]
weights = [int(input()) for _ in range(M)]

parking = {}
for i in range(M + 1):
    parking[i + 1] = []

waiting = deque()
total_fee = 0

parking_idx = [x for x in range(N)]
heapq.heapify(parking_idx)

for i in range(2 * M):
    if parking_idx and waiting:
        car_num = waiting.popleft()
        idx = heapq.heappop(parking_idx)
        parking[car_num] = [idx, fees[idx], weights[car_num - 1]]

    car_num = int(input())
    if car_num > 0:  # 입차
        if parking_idx:
            idx = heapq.heappop(parking_idx)
            parking[car_num] = [idx, fees[idx], weights[car_num - 1]]
        else:
            waiting.append(car_num)

    else:
        car_num = abs(car_num)
        idx = parking[car_num][0]
        fee = parking[car_num][1]
        weight = parking[car_num][2]
        total_fee += fee * weight
        heapq.heappush(parking_idx, idx)

print(total_fee)

출처: [백준] 3190번 뱀

문제

‘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가 증가하는 순으로 주어진다.

출력

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

예제 입력 1

1
2
3
4
5
6
7
8
9

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

예제 출력 1

1

9

예제 입력 2

1
2
3
4
5
6
7
8
9
10
11

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

예제 출력 2

1

21

예제 입력 3

1
2
3
4
5
6
7
8
9
10
11
12

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

예제 출력 3

1

13

출처

• Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #1 - Juniors 2번
  • 문제의 오타를 찾은 사람: dlwocks31, hax3
  • 빠진 조건을 찾은 사람: doju, joonas, zhsks311
  • 문제를 번역한 사람: sehun

알고리즘 분류

• 구현
• 자료 구조
• 시뮬레이션
• 덱
• 큐

소스코드

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

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
board = [[0] * (N) for _ in range(N)]  # NxN 보드 생성

K = int(input())  # 사과 개수
for _ in range(K):  # 사과 위치 지정 0:없음, 1:있음
    y, x = map(int, input().split())
    board[y - 1][x - 1] = 2

# 우, 하, 좌, 상 // 시계방향
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

L = int(input())  # 방향 전환 횟수
times = deque()
directions = deque()
for _ in range(L):
    time, dire = input().rstrip().split()
    times.append(int(time))
    directions.append(dire)

count = 0
direction = 0
nx, ny = 0, 0  # 초기위치
visited = deque([[ny, nx]])

while True:
    count += 1
    # 칸 이동
    nx += dx[direction]
    ny += dy[direction]
    if 0 <= nx < N and 0 <= ny < N and board[ny][nx] != 1:  # 보드 체크
        # 사과가 있으면 그냥 추가, 없으면 꼬리 제거하고 추가
        if board[ny][nx] == 0:  # 사과가 없으면
            temp_y, temp_x = visited.popleft()
            board[temp_y][temp_x] = 0  # 꼬리 줄어듬
        board[ny][nx] = 1
        visited.append([ny, nx])

    else:
        print(count)
        exit(0)

    if count in times:
        dire = directions.popleft()
        if dire == 'D':
            direction += 1
            if direction > 3:
                direction = 0
        else:
            direction -= 1
            if direction < 0:
                direction = 3