티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 구현, 문자열, 그리디 알고리즘
문제
수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.
이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
문자열의 뒤에 A를 추가한다.
문자열을 뒤집고 뒤에 B를 추가한다.
주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)
출력
S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.
예제 입출력
Algorithm
완전 탐색 이용 1. T에서 가장 맨 뒤에 A가 있다면 A 빼기 2. T에서 가장 맨 뒤에 B가 있다면 B 빼고 reverse 3. 1, 2 과정 후 S와 동일한지 확인 4. T의 길이가 0이 되면 BREAK
Code
import sys
input = sys.stdin.readline
S = input().rstrip()
T = input().rstrip()
answer = '0'
while T:
# T의 가장 맨 뒤에 A가 있다면 A 빼기
if T[-1] == 'A':
T = T[:-1]
else: # T의 가장 맨 뒤에 B가 있다면 B 빼고 reverse
T = T[:-1]
T = T[::-1]
# T의 값이 S와 같으면 break
if T == S:
answer = '1'
break
print(answer)
티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 구현, 브루트포스 알고리즘
문제
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.
아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.
테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.
입력
첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)
둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.
출력
첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.
예제 입출력
Algorithm
완전 탐색 이용 1. 테트로미노의 모든 경우의 수마다 도느 좌표의 합을 구해 최댓값 갱신 ☞ 테트로미노마다 회전과 대칭을 고려해야 함
고려해야 하는 경우의 수가 총 19개 1. 파란색 도형 : 90도 회전 2. 노란색 도형 : 고려할 변형 도형 없음 3. 주황색 도형 : 90도 회전, 180도 회전, 270도 회전, 90도 회전 후 상하대칭, 90도 회전 후 좌우대칭, 상하대칭, 좌우대칭 4. 초록색 도형 : 90도 회전, 90도 회전 후 좌우대칭, 상하대칭 5. 분홍색 도형 : 90도 회전, 180도 회전, 270도 회전
모든 케이스의 반례를 공유해놓은 글이 있어 많은 도움이 되었다. https://www.acmicpc.net/board/view/61597
Code
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
max_sum = 0
# 1번 도형 확인
for i in range(N):
for j in range(M-3):
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i][j+3]
# 1번 도형 회전 확인
for i in range(N-3):
for j in range(M):
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+3][j]
# 2번 도형 확인
for i in range(N-1):
for j in range(M-1):
if board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j] + board[i+1][j+1]
# 3번 도형, 3번 도형 변형, 4번 도형, 5번 도형 변형 확인
for i in range(N-2):
for j in range(M-1):
# 3번 도형
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+2][j+1]
# 3번 도형 180도 회전 도형
if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j+1]
# 3번 도형 오른쪽으로 270도 회전 도형
if board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j+1]
# 3번 도형 좌우 대칭 도형
if board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j+1] + board[i+1][j+1] + board[i+2][j+1] + board[i+2][j]
# 4번 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
# 4번 도형 상하 대칭 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]
# 5번 도형 오른쪽으로 90도 회전 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j+1]
# 5번 도형 오른쪽으로 270도 회전 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j]
# 3번 도형 변형, 4번 도형 변형, 5번 도형, 5번 도형 변형 확인
for i in range(N-1):
for j in range(M-2):
# 3번 도형 오른쪽으로 90도 회전 도형
if board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j+2]
# 3번 도형 상하 대칭 도형
if board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2] > max_sum:
max_sum = board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j+2]
# 3번 도형 오른쪽으로 90도 회전 후 상하 대칭 도형
if board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
# 3번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+2]
# 4번 도형 오른쪽으로 90도 회전 도형
if board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1] > max_sum:
max_sum = board[i][j+1] + board[i][j+2] + board[i+1][j] + board[i+1][j+1]
# 4번 도형 오른쪽으로 90도 회전 후 좌우 대칭 도형
if board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j+2]
# 5번 도형
if board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1] > max_sum:
max_sum = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j+1]
# 5번 도형 180도 회전 도형
if board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] > max_sum:
max_sum = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j+2]
print(max_sum)
티어 : Gold 5 시간 제한 : 2 초 메모리 제한 : 256 MB 알고리즘 분류 : 브루트포스 알고리즘
문제
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
입력
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
출력
첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.
예제 입출력
힌트
예제 1의 경우 5455++ 또는 5459--
Algorithm
완전 탐색 이용 1. 고장난 버튼을 제거하고 찾는 채널과 가장 가까운 수 만들기 2. 해당 숫자의 자리수 + (찾는 채널 - 만든 수) Return
고려해야 할 조건들이 너무 많아 힘들었던 문제 ㅠㅠ
Code
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
error_key = []
if M > 0:
error_key = list(map(int, input().split()))
# 사용 가능한 키는 True, 그렇지 않으면 False
error_keys = dict()
for i in range(10):
if i not in error_key:
error_keys[i] = True
else:
error_keys[i] = False
# 보고싶은 채널과 가장 가까운 숫자 만들기
one_step = 5000011
# 찾는 채널보다 작은 수로 가까운 숫자 만들기
for num in range(N, -1, -1):
# 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
if N == 100 or M == 0 or M == 10:
break
# keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
temp = list(str(num))
# error_key가 아닌 key 개수 세기
count = 0
for i in temp:
if error_keys[int(i)]:
count += 1
# count가 temp의 길이와 같으면 만들 수 있는 숫자
if count == len(temp):
one_step = num
break
# 찾는 채널보다 큰 수로 가까운 숫자 만들기
num = N
while True:
# 찾는 채널이 100이거나 M이 0이거나 숫자가 모두 고장이면 break
if N == 100 or M == 0 or M == 10:
break
# keys 중 error_key에 없는 숫자를 이용해 해당 숫자 만들 수 있으면 break
temp = list(str(num))
# error_key가 아닌 key 개수 세기
count = 0
for i in temp:
if error_keys[int(i)]:
count += 1
# count가 temp의 길이와 같으면 만들 수 있는 숫자
if count == len(temp):
# 찾는 채널보다 작은 채널의 숫자 차이가 작으면 갱신
if one_step < N:
if N - one_step > num - N:
one_step = num
break
else:
one_step = num
break
if one_step < N and num - N >= N - one_step:
break
num += 1
answer = 0
if N != 100:
if M == 10 or one_step == 5000011:
if M == 0:
answer = min(max(100-N, N-100), len(str(N)))
else:
answer = max(N - 100, 100-N)
# 100에서 +와 -만을 이용해 움직인 횟수가 one_step과의 차이보다 작으면 갱신
elif max(100-N, N-100) < max(N-one_step, one_step-N) + len(str(N)):
if one_step == 5000011:
answer = min(max(100-N, N-100), len(str(N)))
else:
answer = max(100-N, N-100)
# 숫자 중 고장난 키가 하나도 없으면 채널 번호 길이만큼 출력
elif M == 0:
answer = len(str(N))
else:
answer = len(str(one_step))
answer += max(N - one_step, one_step - N)
print(str(answer))
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 구현, 브루트포스 알고리즘
문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입출력
힌트
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
Algorithm
1. 사탕의 색상을 2차원 리스트 board에 저장 2. board를 하나씩 확인하면서 행에 같은 사탕이 몇 개인지 세기 2.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 2.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 3. board를 하나씩 확인하면서 열에 같은 사탕이 몇 개인지 세기 3.1. 행: board[i][j]부터 board[i][j+1]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue 3.2. 열: board[i][j]부터 board[i+1][j]까지 같은 색이면 count + 1 다른 색이면 count 1로 초기화하고 continue
Code
import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
board.append(list(input().rstrip()))
# 행을 기준으로 다른 색상 교환
max_count = 1
for i in range(N):
for j in range(N-1):
# 인접한 행의 색상이 다르면 교환
if board[i][j] != board[i][j+1]:
board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
# 교환했을 때 사탕의 최대 개수 체크
# 행 확인
for x in range(N):
count = 1
for y in range(N-1):
# 인접한 행의 색상이 같으면 count 증가
if board[x][y] == board[x][y+1]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 열 확인
for y in range(N):
count = 1
for x in range(N-1):
# 인접한 열의 색상이 같으면 count 증가
if board[x][y] == board[x+1][y]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 교환했던 칸 원위치
board[i][j], board[i][j+1] = board[i][j+1], board[i][j]
# 열을 기준으로 다른 색상 교환
for j in range(N):
for i in range(N-1):
# 인접한 열의 색상이 다르면 교환
if board[i][j] != board[i+1][j]:
board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
# 교환했을 때 사탕의 최대 개수 체크
# 행 확인
for x in range(N):
count = 1
for y in range(N-1):
# 인접한 행의 색상이 같으면 count 증가
if board[x][y] == board[x][y+1]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 열 확인
for y in range(N):
count = 1
for x in range(N-1):
# 인접한 열의 색상이 같으면 count 증가
if board[x][y] == board[x+1][y]:
count += 1
else: # 같지 않으면 count 1로 초기화하고 다음 칸 확인
if max_count < count:
max_count = count
count = 1
continue
if max_count < count:
max_count = count
# 교환했던 칸 원위치
board[i][j], board[i+1][j] = board[i+1][j], board[i][j]
print(max_count)
티어 : Bronze 2 시간 제한 : 2 초 메모리 제한 : 128 MB 알고리즘 분류 : 브루트포스 알고리즘, 정렬
문제
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
예제 입출력
Algorithm
완전 탐색 이용 1. 난쟁이의 키를 리스트로 입력 2. 두 개씩 뺀 후 리스트의 합이 100이 되는지 확인
Code
import sys
input = sys.stdin.readline
heights = [0 for _ in range(9)]
for i in range(9):
heights[i] = int(input())
# 리스트 오름차순
heights.sort()
# 리스트에서 두개씩 빼어 리스트의 합이 100이 되는지 확인
temp = []
for i in range(len(heights)):
for j in range(i, len(heights)):
if sum(heights[:i]+heights[i+1:j]+heights[j+1:]) == 100:
temp += heights[:i] + heights[i+1:j] + heights[j+1:]
break
if len(temp) > 0:
break
answer = ''
for i in temp:
answer += str(i) + '\n'
print(answer)
티어 : Silver 2 시간 제한 : 0.5 초 (추가 시간 없음) 메모리 제한 : 512 MB 알고리즘 분류 : 수학, 정수론
문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 g(N)를 출력한다.
예제 입출력
Algorithm
N까지의 약수 중 i라는 숫자는 N//i개 존재 -> i가 1부터 N까지 증가하면서 i의 개수 * i 더하기
티어 : Silver 4 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 구현, 자료 구조, 큐
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입출력
Algorithm
Queue 구현 - deque library 사용 1. queue에 1부터 N까지 숫자로 채움 2. append(queue[0]), popleft()를 두 번 수행 3. print(queue[0]), popleft() 수행 4. queue가 빌 때까지 반복
Code
from collections import deque
N, K = map(int, input().split())
queue = deque([i for i in range(1, N+1)])
answer = []
while queue:
# append, popleft 두 번 수행
for _ in range(K - 1):
queue.append(queue[0])
queue.popleft()
# print, popleft 수행
answer.append(queue[0])
queue.popleft()
print('<', end = '')
for i in range(len(answer)):
if i == len(answer) - 1:
print(answer[i], end = '>')
else:
print(answer[i], end = ', ')
티어 : Silver 2 시간 제한 : 2 초 (추가 시간 없음) 메모리 제한 : 128 MB 알고리즘 분류 : 자료 구조, 큐
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입출력
Algorithm
Queue 구현 - deque library 사용 1. queue에 1부터 n까지 숫자로 채움 2. popleft()로 맨 위의 카드 버림 3. append(queue[0])로 맨 위의 카드 맨 마지막으로 보내기 4. popleft()로 맨 위의 카드 버림 5. 카드가 한 장 남을 때까지 반복
Code
from collections import deque
N = int(input())
queue = deque([i for i in range(1, N+1)])
while len(queue) > 1:
# 맨 위의 카드 버리기
queue.popleft()
# 그 다음 맨 위의 카드 버리고 캔 아래 카드 아래로 보내기
queue.append(queue[0])
queue.popleft()
print(queue[0])
