Open robert-min opened 7 months ago
"""
Return : 너비가 가장 넓은 레벨, 그 레벨의 너비를 출력
- 각 레벨의 가장 왼쪽 - 가장 오른쪽 + 1 = 그 레벨의 너비
- node의 depth기준으로 탐색
- node.level, node.width, node.left, node.right
- node.level => 그래프 그리면서 부모 노드의 left += 1
- node의 width는 어떻게? => 모든 노드가 다 그려진 후 중위순회로 탐색 += 1
- node의 width의 최대 최소 값을 all_width[level] = [min, max]로 저장 -> 저장후 비교
"""
import sys
input = sys.stdin.readline
N = int(input())
nodes = [[-1, -1] for _ in range(N+1)]
is_root = [True] * (N+2)
for _ in range(N):
node, left, right = map(int, input().split())
is_root[left] = False
is_root[right] = False
nodes[node][0] = left
nodes[node][1] = right
# 중위 순회
cur_width = 1
max_height = -1
height_list = [[] for _ in range(N+1)]
def inorder(cur, height):
global cur_width, max_height
max_height = max(max_height, height)
if nodes[cur][0] != -1:
inorder(nodes[cur][0], height + 1)
# 높이별 현재의 width 저장
height_list[height].append(cur_width)
cur_width += 1
if nodes[cur][1] != -1:
inorder(nodes[cur][1], height+1)
inorder(is_root[1:-1].index(True) + 1, 1)
answer_width, answer_height = -1, -1
for level in range(1, max_height + 1):
max_width_diff = height_list[level][-1] - height_list[level][0] + 1
if answer_width < max_width_diff:
answer_width = max_width_diff
answer_height = level
print(answer_height, answer_width)
"""
Return : 어졌을 때 상단에 쓰여있는 값 출력
- 가장 처음 주사위 모든면이 0
- 주사위 놓여있는 칸에는 0, 지도의 각 칸에 정수
- 이동한 칸에 쓰여있는 수 0 -> 주사위 바닥면에 쓰여있는 수가 칸에 복사
- 0이 아니면 -> 칸에 스여있는 수가 주사위에 복사
- 주사위 놓은 곳 좌표와 이동 명령이 주어졌을 때 상단에 쓰여있는 값 출력
- order에 따라 이동
- 이동한 방향에 따라 주사위 상단면 하단면 위치 변경(move)
1. 주사위를 굴린다 (명령어의 개수만큼)
2. 주사위를 굴린 후 조건에 따라 주사위 밑면의 숫자를 변경
3. 이동한 칸이 == 0 -> 주사위 바닥면의 수 칸에 복사
4. 이동한 칸이 = 0 -> 칸에 쓰여있는 수 바닥면에 복사
5. 좌표 조건 추가해주기!!!
"""
import sys
input = sys.stdin.readline
N, M, x, y, K = map(int, input().split())
matrix = []
for _ in range(N):
matrix.append(list(map(int, input().split())))
# 1 동쪽, 2 서쪽, 3 북쪽, 4 남쪽
# 바깥으로 이동할 경우 무시. 출력X
orders = list(map(int, input().split()))
dice = [0] * 6
dr = [0, 0, 0, -1, 1]
dc = [0, 1, -1, 0, 0]
for order in orders:
nx = x + dr[order]
ny = y + dc[order]
if not 0 <= nx < N or not 0 <= ny < M: continue
east, west, south, north, up, down = dice[0], dice[1], dice[2], dice[3], dice[4], dice[5]
# east
if order == 1:
dice[0], dice[1], dice[4], dice[5] = down, up, east, west
# west
elif order == 2:
dice[0], dice[1], dice[4], dice[5] = up, down, west, east
# north
elif order == 3:
dice[2], dice[3], dice[4], dice[5] = up, down, north, south
# south
elif order == 4:
dice[2], dice[3], dice[4], dice[5] = down, up, south, north
if matrix[nx][ny] == 0:
matrix[nx][ny] = dice[5]
else:
dice[5] = matrix[nx][ny]
matrix[nx][ny] = 0
x, y = nx, ny
print(dice[4])
"""
Return : 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수
"""
import sys
input = sys.stdin.readline
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, 1000001):
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009
for _ in range(int(input())):
num = int(input())
print(dp[num])
문제