출처: [백준] 2720번 세탁소 사장 동혁

문제

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.

동혁이는 리암에게 실망했다.

리암은 거스름돈을 주는 것을 자꾸 실수한다.

심지어 $0.5달러를줘야하는경우에거스름돈으로$5달러를 주는것이다!

어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의개수,다임(Dime,$0.10)의 개수, 니켈(Nickel, $0.05)의개수,페니(Penny,$0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00이하이고,손님이받는동전의개수를최소로하려고한다.예를들어,$1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

예제 입력 1

1
2
3
4

3
124
25
194

예제 출력 1

1
2
3

4 2 0 4
1 0 0 0
7 1 1 4

출처

• ICPC > Regionals > North America > Greater New York Region > 2006 Greater New York Programming Contest A번
  • 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 그리디 알고리즘
• 사칙연산

소스코드

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

import sys

input = sys.stdin.readline
T = int(input())

# quarter = 25
# Dime = 10
# Nickel = 5
# Penny = 1
for _ in range(T):
    quarter, dime, nickel, penny = 0, 0, 0, 0  # 각 동전 개수
    C = int(input())
    while C > 0:
        if C >= 25:  # Quarter
            quarter += C // 25
            C %= 25
        elif C >= 10:  # Dime
            dime += C // 10
            C %= 10
        elif C >= 5:  # Nickel
            nickel += C // 5
            C %= 5
        elif C >= 1:  # Penny
            penny += C // 1
            C -= penny

    print(quarter, dime, nickel, penny)

출처: [백준] 1789번 수들의 합

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

예제 입력 1

1

200

예제 출력 1

1

19

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: newton08, upple1

알고리즘 분류

• 수학
• 그리디 알고리즘

소스코드

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

import sys

input = sys.stdin.readline

S = int(input())

N, i = 0, 1
while True:
    N += i
    if N > S:
        print(i - 1)
        break
    elif N == S:
        print(i)
        break
    i += 1

출처: [백준] 10162번 전자레인지

문제

3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다.

냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A, B, C를 누른 횟수의 합은 항상 최소가 되어야 한다. 이것을 최소버튼 조작이라고 한다.

만일 요리시간이 100초라고 하면(T=100) B를 1번, C는 4번 누르면 된다. 이와 다르게 C를 10번 눌러도 100초가 되지만 이 경우 10번은 최소 횟수가 아니기 때문이 답이 될 수 없다. 이 경우 B 1번, C 4번, 총 5번이 최소버튼 조작이다. 그리고 T=234와 같이 3개의 버튼으로 시간을 정확히 맞출 수 없는 경우도 있다.

여러분은 주어진 요리시간 T초를 맞추기 위한 최소버튼 조작 방법을 구하는 프로그램을 작성해야 한다.

입력

첫 번째 줄에는 요리시간 T(초)가 정수로 주어져 있으며 그 범위는 1 ≤ T ≤ 10,000 이다.

출력

여러분은 T초를 위한 최소버튼 조작의 A B C 횟수를 첫 줄에 차례대로 출력해야 한다. 각각의 횟수 사이에는 빈 칸을 둔다. 해당 버튼을 누르지 않는 경우에는 숫자 0을 출력해야한다. 만일 제시된 3개의 버튼으로 T초를 맞출 수 없으면 음수 -1을 첫 줄에 출력해야 한다.

서브태스크

예제 입력 1

1

100

예제 출력 1

1

0 1 4

예제 입력 2

1

189

예제 출력 2

1

-1

출처

• Olympiad > 한국정보올림피아드 > KOI 2014 > 초등부 1번
  • 문제의 오타를 찾은 사람: 79brue, ojh3316
  • 데이터를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 구현
• 그리디 알고리즘

소스코드

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

import sys

input = sys.stdin.readline

T = int(input())

control = [300, 60, 10]
count = [0, 0, 0]
for i in range(3):
    if T >= control[i]:
        count[i] = T // control[i]
        T %= control[i]

if not T:
    print(*count)
else:
    print(-1)

출처: [백준] 10820번 문자열 분석

문제

문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오.

각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열의 길이는 100을 넘지 않는다.

예제 입력 1

1
2
3
4

This is String
SPACE    1    SPACE
 S a M p L e I n P u T     
0L1A2S3T4L5I6N7E8

예제 출력 1

1
2
3
4

10 2 0 2
0 10 1 8
5 6 0 16
0 8 9 0

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 구현
• 문자열

소스코드

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

import sys

input = sys.stdin.readline

while True:
    input_string = input().rstrip('\n')

    if not input_string:
        break

    lower, upper, digit, space = 0, 0, 0, 0

    for ch in input_string:
        if ch.islower():
            lower += 1
        elif ch.isupper():
            upper += 1
        elif ch.isdigit():
            digit += 1
        elif ch.isspace():
            space += 1

    print(f"{lower} {upper} {digit} {space}")

출처: [백준] 13417번 카드 문자열

문제

N장의 카드가 일렬로 놓여있다. 각 카드에는 알파벳이 하나씩 적혀있다. 태욱이는 가장 왼쪽에 있는 카드부터 차례대로 한 장씩 가져올 수 있다. 가장 처음에 가져온 카드는 자신의 앞에 놓는다. 그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. 태욱이는 모든 카드를 다 가져온 후에 자신의 앞에 놓인 카드를 순서대로 이어 붙여 카드 문자열을 만들려고 한다.

예를 들어 3장의 카드가 [M, K, U] 순으로 놓여있다고 하자. 태욱이는 먼저 가장 왼쪽에 있는 “M”이 적힌 카드를 가져와서 자신의 앞에 놓는다. 다음으로 남은 카드 중 가장 왼쪽에 있는 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 다시 가장 왼쪽에 두면 “UKM”이라는 문자열을 만들 수 있다. 만약 “K”가 적힌 카드를 가져와서 가장 왼쪽에 두고, 이어서 “U”가 적힌 카드를 가져와서 가장 오른쪽에 두면 “KMU”라는 문자열을 만들 수 있다. 이때, 태욱이가 만들 수 있는 문자열 중 사전 순으로 가장 빠른 문자열은 “KMU”이다.

N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처음에 놓여있는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N장의 카드에 적힌 알파벳의 초기 순서가 주어진다. 가장 왼쪽에 있는 카드에 적혀있는 알파벳부터 순서대로 N개가 공백으로 구분되어 주어진다. 모든 카드에는 한 개씩의 알파벳이 적혀있으며, 모두 대문자이다.

출력

출력은 표준 출력을 사용한다. 입력받은 데이터에 대해, 한 줄에 1개씩 태욱이가 만들 수 있는 문자열 중에서 사전 순으로 가장 빠른 문자열을 출력한다.

예제 입력 1

1
2
3
4
5
6
7

3
3
M K U
5
A S D F G
7
B A C A B A C

예제 출력 1

1
2
3

KMU
ASDFG
AAABCBC

출처

• University > 국민대학교 > 2016 국민대학교 교내 경시대회 E번
  • 문제를 만든 사람: game2k

알고리즘 분류

• 자료 구조
• 문자열
• 그리디 알고리즘
• 덱

소스코드

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

import sys
from collections import deque

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    card_list = deque(input().rstrip().split())
    new_list = deque(card_list.popleft())

    while card_list:
        temp = card_list.popleft()
        if temp > new_list[0]:
            new_list.append(temp)
        else:
            new_list.appendleft(temp)

    print(''.join(new_list))

출처: [백준] 18115번 카드 놓기

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

예제 입력 1

1
2

5
1 1 1 1 1

예제 출력 1

1

5 4 3 2 1

예제 입력 2

1
2

5
2 3 3 2 1

예제 출력 2

1

1 5 2 3 4

출처

• University > 서강대학교 > 2019 Sogang Programming Contest (Champion) C번
  • 문제를 검수한 사람: jh05013, shiftpsh
  • 문제를 만든 사람: semteo04

알고리즘 분류

• 자료 구조
• 덱

풀이

1
2
3
4

반대로
1) 맨위의 카드를 바닥으로
2) 맨위의 카드를 바닥에서 2번째로
3) 맨위의 카드를 맨위로

소스코드

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 = int(input())
card_list = deque(range(1, N + 1))
commands = list(map(int, input().split()))
init_list = deque()

while commands:
    command = commands.pop()
    temp = card_list.popleft()
    if command == 1:
        init_list.appendleft(temp)
    elif command == 2:
        init_list.insert(1, temp)
    elif command == 3:
        init_list.append(temp)

print(*init_list)

출처: [코딩테스트 연습] 문자열 내 마음대로 정렬하기

문제

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [“sun”, “bed”, “car”]이고 n이 1이면 각 단어의 인덱스 1의 문자 “u”, “e”, “a”로 strings를 정렬합니다.

제한

• strings는 길이 1 이상, 50이하인 배열입니다.
• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
• strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
• 모든 strings의 원소의 길이는 n보다 큽니다.
• 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력

입출력 예 1

“sun”, “bed”, “car”의 1번째 인덱스 값은 각각 “u”, “e”, “a” 입니다. 이를 기준으로 strings를 정렬하면 [“car”, “bed”, “sun”] 입니다.

입출력 예 2

“abce”와 “abcd”, “cdx”의 2번째 인덱스 값은 “c”, “c”, “x”입니다. 따라서 정렬 후에는 “cdx”가 가장 뒤에 위치합니다. “abce”와 “abcd”는 사전순으로 정렬하면 “abcd”가 우선하므로, 답은 [“abcd”, “abce”, “cdx”] 입니다.

풀이

-

소스코드

1
2
3
4
5
6
7
8
9

def solution(strings, n):
    strings.sort()
    answer = sorted(strings, key=lambda x: x[n])
    return answer


print(solution(["sun", "bed", "car"], 1))
print(solution(["abce", "abcd", "cdx"], 2))

출처: [백준] 15501번 부당한 퍼즐

문제

현욱은 퍼즐 게임을 굉장히 좋아한다. 어느 날 현욱은 친구로부터 간단한 플래시 퍼즐 게임을 하나 추천 받았는데, 이 퍼즐 게임은 다음과 같은 규칙을 갖고 있다.

1. 플레이어는 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열을 하나 가지고 시작한다.
2. 또 다른 1 ~ n 까지 숫자가 한 번씩만 나타나는 수열이 주어졌을 때, 처음 수열을 적절히 변형해서 처음 받은 수열을 이 수열과 동일한 수열로 만들어야 한다.
3. 이때, 플레이어가 수열에 대해서 할 수 있는 동작은 다음 두 가지가 있다. 동작은 몇 번이라도 수행할 수 있다.
   • 뒤집기 : 현재 수열을 거꾸로 뒤집는다. ex) 1 2 3 4 5 -> 5 4 3 2 1
   • 밀기 : 현재 수열을 왼쪽 혹은 오른쪽으로 한 칸 민다. ex) 1 2 3 4 5 -> 5 1 2 3 4

퍼즐을 풀던 현욱은 분명히 엄청 쉬운 규칙인데도 불구하고 문제가 안 풀려서, 한참을 고민하다가 다시 잘 비교해보니 정답 수열을 주어진 동작만으로는 절대 만들 수가 없는 문제였다!

화가 난 현욱은 퍼즐 제작자에게 따지기 위해 주어진 문제가 올바른 문제인지 아닌지 확인하는 프로그램을 만들기로 결심했다. 현욱을 도와 괘씸한 퍼즐 제작자를 응징해주자.

입력

첫째 줄에 n이 주어진다(1 ≤ n ≤ 1,000,000).

둘째 줄에 1에서 n까지의 수가 한 번만 나타나는 수열이 순서대로 주어진다.

셋째 줄에 주어진 두 연산을 수행해서 구성할 수 있는지 확인할 1에서 n까지 수가 한 번만 나타나는 수열이 순서대로 주어진다.

출력

주어진 두 가지 연산만을 가지고 처음 수열을 결과 수열로 만들 수 있다면 good puzzle, 아니면 bad puzzle을 출력한다.

예제 입력 1

1
2
3

5
1 2 3 4 5
4 3 2 1 5

예제 출력 1

1

good puzzle

예제 입력 2

1
2
3

5
1 2 3 4 5
1 2 4 3 5

예제 출력 2

1

bad puzzle

출처

• Contest > 소프트콘 > 제1회 소프트콘 A번
  • 문제를 만든 사람: jwvg0425
  • 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 구현
• 자료 구조
• 덱

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

# 순방향
first_idx = compare.index(sequence[0])  # 기준점
new_list1 = compare[first_idx:] + compare[:first_idx]

# 역방향
compare = compare[::-1]
first_idx = compare.index(sequence[0])  # 기준점
new_list2 = compare[first_idx:] + compare[:first_idx]

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
    print("good puzzle")
else:
    print("bad puzzle")

소스코드

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

import sys

input = sys.stdin.readline

N = int(input())
sequence = list(map(int, input().split()))
compare = list(map(int, input().split()))

new_list1 = []
new_list2 = []

first_idx = compare.index(sequence[0])  # 기준점

# 순방향인 경우
start = first_idx - N
end = first_idx

for i in range(start, end):
    new_list1.append(compare[i])

# 역방향인 경우
start = first_idx
end = first_idx - N

for i in range(start, end, -1):
    new_list2.append(compare[i])

# 둘 중 하나 맞으면 good puzzle
if sequence == new_list1 or sequence == new_list2:
    print("good puzzle")
else:
    print("bad puzzle")

'''
5
1 2 3 4 5
3 4 5 1 2

6
1 2 3 4 5 6
3 2 1 6 5 4
4 5 6 1 2 3

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

'''

출처: [2019 카카오 개발자 겨울 인턴십] 크레인 인형뽑기 게임

문제

게임개발자인 “죠르디”는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
“죠르디”는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

crane_game_101.png

게임 화면은 “1 x 1” 크기의 칸들로 이루어진 “N x N” 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 “5 x 5” 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 “1 x 1” 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

crane_game_102.png

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

crane_game_103.gif

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한

• board 배열은 2차원 배열로 크기는 “5 x 5” 이상 “30 x 30” 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력

입출력 예 1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

crane_game_104.jpg

풀이

-

소스코드

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

def solution(board, moves):
    N = len(board)  # 보드의 길이
    answer = 0
    basket = []
    for move in moves:
        for i in range(N):
            if board[i][move - 1] > 0:  # Move별로 맨 위에 있는 인형을 바구니에 넣고, 빈칸으로 전환
                basket.append(board[i][move - 1])
                board[i][move - 1] = 0
                break

        if len(basket) > 1:  # 바구니가 2개이상일 때부터
            if basket[-1] == basket[-2]:  # 가장 최신에 들어온 것과 그 전에 들어온 것이 같으면 두개 삭제
                basket.pop()
                basket.pop()
                answer += 2

    return answer


print(solution([[0, 0, 0, 0, 0], [0, 0, 1, 0, 3], [0, 2, 5, 0, 1], [4, 2, 4, 4, 2], [3, 5, 1, 3, 1]],
               [1, 5, 3, 5, 1, 2, 1, 4]))

출처: [백준] 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())