링크 : https://www.acmicpc.net/problem/9019
from collections import deque
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
a, b = map(int, input().split())
def bfs(v, move):
visited = [0] * (10000+1)
visited[v] = move
q = deque([(v, move)])
while q:
v, move = q.popleft()
if v == b:
print(visited[v])
return
for x in ('D', 'S', 'L', 'R'):
if x == 'D':
value = 2 * v
if value > 9999:
value %= 10000
if visited[value] == 0:
visited[value] = move + 'D'
q.append((value, move+'D'))
elif x == 'S':
value = v - 1
if v == 0: # 문제 잘 읽어야 하는 부분, v-1 == 0이 아니라 v == 0 인 경우임.
value = 9999
if visited[value] == 0:
visited[value] = move + 'S'
q.append((value, move+'S'))
# 123에서 'L' 연산시에는 1230이, 'R' 연산시에는 3012가 출력되어야 한다.
elif x == 'L': # 문자열로 바꿔서 연산 후 숫자로 바꾸는 과정은 시간초과가 걸리기 때문에 다음과 같은 로직이 필요하다.
front = v % 1000
back = v // 1000
value = front * 10 + back
if visited[value] == 0:
visited[value] = move + 'L'
q.append((value, move+'L'))
elif x == 'R': # 문자열로 바꿔서 연산 후 숫자로 바꾸는 과정은 시간초과가 걸리기 때문에 다음과 같은 로직이 필요하다.
front = v % 10
back = v // 10
value = front * 1000 + back
if visited[value] == 0:
visited[value] = move + 'R'
q.append((value, move+'R'))
bfs(a, '')
링크 : https://paris-in-the-rain.tistory.com/94
링크 : https://www.acmicpc.net/problem/9095
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
dp = [0, 1, 2, 4]
for i in range(4, n+1):
dp.append(dp[i-1] + dp[i-2] + dp[i-3])
print(dp[n])
링크 : https://www.acmicpc.net/problem/9375
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
clothes = {}
for _ in range(n):
cloth, item = input().split()
if item in clothes: # 옷의 품목과 가짓수 기록
clothes[item] += 1
else:
clothes[item] = 1
answer = 1
for key, value in clothes.items():
answer *= (value + 1) # 해당 옷을 입는 경우와 안입는 경우를 곱집합으로 계산
print(answer - 1) # -1을 해주는 이유는 옷을 전부 안입는 경우(알몸 상태)를 제거해주기 위함.
링크 : https://www.acmicpc.net/problem/9461
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
dp = [0, 1, 1, 1]
for i in range(4, n+1):
dp.append(dp[i-2] + dp[i-3])
print(dp[n])
링크 : https://www.acmicpc.net/problem/10026
import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
photo = [list(input().strip()) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
ans = []
dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs(x, y):
visited[x][y] = True
q = deque([(x, y)])
while q:
px, py = q.popleft()
for k in range(4):
mx = px + dx[k]
my = py + dy[k]
if 0 <= mx < n and 0 <= my < n:
if photo[mx][my] == photo[px][py] and not visited[mx][my]:
visited[mx][my] = True
q.append((mx, my))
for _ in range(2):
cnt = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i, j)
cnt += 1
ans.append(cnt)
for i in range(n):
for j in range(n):
visited[i][j] = False
if photo[i][j] == 'R':
photo[i][j] = 'G'
print(*ans)
링크 : https://www.acmicpc.net/problem/11047
from sys import stdin
input = stdin.readline
n, k = map(int, input().split())
coin = []
for _ in range(n):
coin.append(int(input()))
coin.sort(reverse=True)
answer = 0
for i in range(n):
if k >= coin[i]:
answer += (k // coin[i])
k %= coin[i]
print(answer)
링크 : https://www.acmicpc.net/problem/11279
import heapq
from sys import stdin
input = stdin.readline
n = int(input())
heap = []
for _ in range(n):
x = int(input())
if x == 0:
if heap:
print(-heapq.heappop(heap))
else:
print(0)
else:
heapq.heappush(heap, -x)