마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.
모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
파이어볼은 4개의 파이어볼로 나누어진다.
나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
질량이 0인 파이어볼은 소멸되어 없어진다.
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.
입력
첫째 줄에 N, M, K가 주어진다.
둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.
서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.
출력
마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.
제한
4 ≤ N ≤ 50
0 ≤ M ≤ N2
1 ≤ K ≤ 1,000
1 ≤ ri, ci≤ N
1 ≤ mi≤ 1,000
1 ≤ si≤ 1,000
0 ≤ di≤ 7
예제 입출력
Algorithm
구현 - Simulation 1. 리스트에 명령들 담음 2. 모든 파이어볼 이동 ☞ graph에 각 칸마다 존재하는 파이어볼의 개수 갱신 3. 그래프 전체를 보면서 값이 2 이상인 경우 질량, 속력, 방향 계산해 명령을 담는 리스트에 추가 ☞ 질량이 0이면 추가하지 않음 4. K번째 명령이 끝아면 질량의 총합 구함
Code
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = [[[] for _ in range(N)] for _ in range(N)]
orders = []
for _ in range(M):
r, c, m, s, d = map(int, input().split())
orders.append((r-1, c-1, m, s, d))
graph[r-1][c-1].append((m, s, d))
# 상, 우상향, 우, 우하향, 하, 좌하향, 좌, 좌상향
directions = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
for count in range(K):
# 파이어볼 이동
for r, c, m, s, d in orders:
dx = directions[d][0] * s
dy = directions[d][1] * s
graph[r][c] = graph[r][c][1:]
graph[(r+dx)%N][(c+dy)%N].append((m, s, d))
orders = []
for x in range(N):
for y in range(N):
# 파이어볼이 1개인 칸은 다음 명령에 추가
if len(graph[x][y]) == 1:
m, s, d = graph[x][y][0]
orders.append((x, y, m, s, d))
# 파이어볼이 2개 이상인 칸에서
elif len(graph[x][y]) > 1:
# 질량, 속력, 방향 구하기
sum_m = 0
sum_s = 0
check_d = [0, 0]
for m, s, d in graph[x][y]:
sum_m += m
sum_s += s
check_d[d%2] += 1
m = sum_m // 5
# 질량이 0인 파이어볼 소멸
if m == 0:
graph[x][y] = []
continue
s = sum_s // len(graph[x][y])
# 파이어볼 뱡향이 모두 홀수이거나 짝수이면 0, 2, 4, 6
graph[x][y] = []
if check_d[0] * check_d[1] == 0:
for d in range(0, 7, 2):
orders.append((x, y, m, s, d))
graph[x][y].append((m, s, d))
else:
for d in range(1, 8, 2):
orders.append((x, y, m, s, d))
graph[x][y].append((m, s, d))
# graph에 있는 질량의 합 구하기
answer = 0
for x in range(N):
for y in range(N):
for m, s, d in graph[x][y]:
answer += m
print(answer)
티어 : Gold 5 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션
문제
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
<그림 1> 원래 치즈 모양
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 2> 한 시간 후의 치즈 모양<그림 3> 두 시간 후의 치즈 모양
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
예제 입출력
Algorithm
DFS - 재귀, 구현 1. 1시간마다 DFS를 이용해 치즈에 구멍이 있는지 확인 ☞ 0으로된 덩어리가 2개 이상인 경우 구멍 존재 2. 구멍이 존재하면 구멍에 해당하는 칸의 값을 H로 변경 3. graph를 한 번씩 돌면서 현재 위치가 1인데 상, 하, 좌, 우 중 한 칸이라도 0이 존재하면 이번에 삭제되는 칸 ☞ 해당 칸의 값을 C로 변경 4. 매 번 C의 개수와 1의 개수의 차를 확인해 0인 경우 반복문 break
Code
def dfs(x, y, replace_value):
# graph 밖으로 벗어나면 False Return
if x < 0 or x > N-1 or y < 0 or y > M-1:
return False
# 이미 방문했던 칸이거나 0이 아니면 False Return
if visited[x][y] or graph[x][y] != 0:
return False
# 현재 위치 방문 기록
visited[x][y] = True
# 구멍인 경우 H로 변경
graph[x][y] = replace_value
# 상하좌우로 이동
dfs(x-1, y, replace_value)
dfs(x+1, y, replace_value)
dfs(x, y-1, replace_value)
dfs(x, y+1, replace_value)
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
sys.setrecursionlimit(N*M)
graph = []
count_cheezes = 0 # 치즈가 녹기 전 치즈조각이 놓여 있는 칸의 개수
for _ in range(N):
graph.append(list(map(int, input().split())))
count_cheezes += graph[-1].count(1)
num = 0
while True:
# 구멍의 값을 H로 변경
visited = [[False for _ in range(M)] for _ in range(N)]
for x in range(N):
for y in range(M):
# x, y가 0, 0이 아니면 replace 값 H로 설정
if x > 0 and y > 0:
dfs(x, y, 'H')
else:
dfs(x, y, 0)
# 가장자리에 있는 1을 C로 변경
count_c = 0
for x in range(N):
for y in range(M):
if graph[x][y] == 1:
# 현재 index의 상하좌우 중 한 군데라도 0이 있으면 가장자리
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx = x+dx
ny = y+dy
# graph 밖으로 벗어나면 continue
if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
continue
# nx, ny가 0이면 x, y를 C로 변경하고 break
if graph[nx][ny] == 0:
graph[x][y] = 'C'
count_c += 1
break
# 현재 1인 칸과 없어질 칸의 차가 0이면 break
if count_cheezes - count_c == 0:
print(num+1)
print(count_cheezes)
break
# C, H인 칸 모두 0으로 변경
for x in range(N):
for y in range(M):
if graph[x][y] == 'C'or graph[x][y] == 'H':
graph[x][y] = 0
num += 1
count_cheezes -= count_c
티어 : Silver 5 시간 제한 : 2 초 메모리 제한 : 128 MB 알고리즘 분류 : 구현, 문자열
문제
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.
출력
첫째 줄에 그룹 단어의 개수를 출력한다.
예제 입출력
Algorithm
1. 입력 받은 단어를 한 글자 씩 보면서 리스트에 이미 들어있는지 확인 2. 이미 들어있는 글자가 있다면 다음 단어 확인 3. 끝까지 이미 들어있는 글자가 없다면 그룹 단어
Code
import sys
input = sys.stdin.readline
N = int(input())
answer = 0
for _ in range(N):
word = input().rstrip()
check = [word[0]]
flag = True # 그룹 단어인 경우 True
for index in range(1, len(word)):
# 이전 index의 글자와 현재 index의 글자가 같으면 continue
if word[index-1] == word[index]:
continue
# 현재 index의 글자가 이미 리스트에 들어있다면 다음 단어 확인
if word[index] in check:
flag = False
break
elif index == len(word)-1:
flag = True
check.append(word[index])
# flag가 True인 경우 그룹 단어
if flag:
answer += 1
print(answer)
티어 : Silver 5 시간 제한 : 1.5 초 메모리 제한 : 4 MB 알고리즘 분류 : 구편, 비트마스킹
문제
비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.
add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.
입력
첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.
둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.
출력
check연산이 주어질때마다, 결과를 출력한다.
예제 입출력
Algorithm
구현 - Simulation 문제에 따라서 진행
Code
import sys
input = sys.stdin.readline
M = int(input())
S = []
for _ in range(M):
orders = input().rstrip()
# add x 이면 S에 x 추가
if orders[:3] == 'add':
order, x = orders.split()
# S에 이미 x가 있는 경우 연산 무시
if int(x) in S:
continue
S.append(int(x))
# remove x : S에서 x를 제거
elif orders[:6] == 'remove':
order, x = orders.split()
# S에 x가 없는 경우 연산 무시
if int(x) not in S:
continue
S.remove(int(x))
# check x : S에 x가 있으면 1, 없으면 0 반환
elif orders[:5] == 'check':
order, x = orders.split()
if int(x) in S:
print(1)
else:
print(0)
# toggle x : S에 x가 있으면 x 제거, 없으면 x 추가
elif orders[:6] == 'toggle':
order, x = orders.split()
if int(x) in S:
S.remove(int(x))
else:
S.append(int(x))
# all : S를 {1, 2, ... , 20}으로 변환
elif orders == 'all':
S = list(range(1, 21))
# empty : S를 공집합으로 변경
elif orders == 'empty':
S = []
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 256 MB 알고리즘 분류 : 수학, 구현, 조합론
문제
1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.
사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.
N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
입력
첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.
출력
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
예제 입출력
Algorithm
Greedy 이용 1. 입력 순열을 리스트로 받음 2. N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력 3. 리스트의 마지막 숫자가 1보다 크면 3.1. 리스트의 끝에서부터 내림차순 정렬되어있는 부분 모두 pop 3.2. 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함 4. 리스트의 마지막 숫자가 1이면 4.1. pop하고 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함 5. 남은 자리수 stack에 포함되어있지 않은 값으로 채우기
Code
N = int(input())
stack = list(map(int, input().split()))
# N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
if N == 1 or stack == list(range(1, N+1)):
print(-1)
else:
# 리스트의 마지막 숫자가 1보다 크면
if stack[-1] > 1:
# 리스트의 끝에서부터 처음으로 가면서 내림차순 정렬되어있는 부분 모두 pop
for index in range(N-1, 0, -1):
if stack[index-1] < stack[index]:
stack.pop()
else:
break
stack.pop()
# 다음에 들어가야할 숫자 저장
next_num = (stack[-1] - 1) % (N+1)
if next_num == 0:
next_num = N-1
while next_num in stack:
next_num = (next_num - 1) % (N+1)
if next_num == 0:
next_num = N-1
# 리스트의 마지막 원소를 새로운 숫자로 변경
stack.pop()
stack.append(next_num)
# 리스트 나머지 자리 채우기
for num in range(N, 0, -1):
if num not in stack:
stack.append(num)
else:
stack.pop()
# 다음에 들어가야할 숫자 저장
next_num = (stack[-1] - 1) % (N+1)
if next_num == 0:
next_num = N-1
while next_num in stack:
next_num = (next_num - 1) % (N+1)
if next_num == 0:
next_num = N-1
# 리스트의 마지막 원소를 새로운 숫자로 변경
stack.pop()
stack.append(next_num)
# 리스트 나머지 자리 채우기
for num in range(N, 0, -1):
if num not in stack:
stack.append(num)
print(' '.join(list(map(str, stack))))
