one Book a Day

자주 나오는 문제. 처음엔 거리 계산해서 안움직이고 풀려했는데 실패. 아래에 안움직이는 코드도 찾아놓음. import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) position = list(map(int, input().split())) q = deque([i for i in range(1, n+1)]) move = 0 for num in position: if q.index(num) < len(q)/2: while q[0] != num: q.rotate(-1) move += 1 else: while q[0] != num: q.rotate(1) move += 1 if q[0] ==..

dp의 구성은 숫자 n을 만드는데 쓰는 숫자의 갯수(0~n개까지 썼을 시의 모든 경우를 계산) import sys input = sys.stdin.readline MOD = 1000000009 # 숫자 n을 m개를 써서 만드는 경우의 수. n * n 까지 가능. dp = [[0] * 1001 for _ in range(1001)] dp[1][1] = 1 dp[2][1] = 1 dp[2][2] = 1 dp[3][1] = 1 dp[3][2] = 2 dp[3][3] = 1 for i in range(4, 1001): for j in range(1, i + 1): dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 1] + dp[i - 3][j - 1]) % MOD for _ in ..

각 조합마다 bfs 돌려서 최소값을 비교해줍니다. import sys input = sys.stdin.readline from collections import deque from itertools import combinations def bfs(q): visited = [[False] * N for _ in range(N)] for x, y in q: visited[x][y] = True time = -1 cnt = len(q) while q: for _ in range(len(q)): x, y = q.popleft() for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0

최대 정사각형 만들기 or 직사각형 만들기와 동일한 로직. W가 나오면 초기화, 나오지 않으면 최소거리 갱신하며 dp 양방향으로 한번씩 하고 그 중 최솟값으로 갱신. import sys sys.stdin = open('input.txt') for test in range(1, int(input()) + 1): N, M = map(int, input().split()) pool = [list(input()) for _ in range(N)] dp = [[float('inf')] * M for _ in range(N)] answer = 0 for i in range(N): for j in range(M): if pool[i][j] == 'W': dp[i][j] = 0 continue if j: dp[i][j..

bfs로 갈수 있는 영역 전부 순회. 현재 터널의 타입과 다음 갈 칸의 타입을 비교해 연결되어 있을 때만 이동하도록 설계 import sys sys.stdin = open('input.txt') from collections import deque def bfs(x, y, cur_type, time): q = deque() q.append((x, y, cur_type, time)) visited[x][y] = True answer = 1 while q: x, y, cur_type, time = q.popleft() for direction in tunnels[cur_type]: nx, ny = x + dx[direction], y + dy[direction] if 0

dp로 최솟값만 끌고가며 연산한다. for test in range(1, int(input()) + 1): # 0, 1, 2, 3: 1일, 1달, 3개월, 1년 costs = list(map(int, input().split())) annual_plans = [0] + list(map(int, input().split())) dp = [0] * 13 for i in range(1, 13): dp[i] = dp[i-1] + min(costs[0] * annual_plans[i], costs[1]) if i > 2: dp[i] = min(dp[i], dp[i-3] + costs[2]) answer = min(dp[12], costs[3]) print(f'#{test} {answer}')

1. 가장 높은 봉우리에서 탐색 2. k만큼 땅을 팠다가 복구 def dfs(x, y, cnt): global answer answer = max(answer, cnt) for i in range(4): nx, ny = x + dx[i], y + dy[i] if 0 = k: mountain[i][j] -= k new_start(candidates) mountain[i][j] += k for test in range(1, int(input()) + 1): N, K = map(int, input().split()) mountain = [list(map(int, input().split())) for _ in range(N)] visited = [[False] * N for _ in range(N)] answ..

중위순횐줄 알았는데 제대로보니 중위는 아니고. 그냥 말단부터 올라오는 분할정복. import sys sys.stdin = open('input.txt') def inorder_tree(cur_node): if not tree[cur_node]: return int(values[cur_node]) left = inorder_tree(tree[cur_node][0]) right = inorder_tree(tree[cur_node][1]) if values[cur_node] == '-': return left - right elif values[cur_node] == '+': return left + right elif values[cur_node] == '*': return left * right else:..

이진탐색트리의 중위 순회 import sys sys.stdin = open('input.txt') def inorder_tree(cur_node): if not tree[cur_node]: return values[cur_node] elif len(tree[cur_node]) == 1: return inorder_tree(tree[cur_node][0]) + values[cur_node] return inorder_tree(tree[cur_node][0]) + values[cur_node] + inorder_tree(tree[cur_node][1]) for test in range(1, 11): N = int(input()) tree = {i: [] for i in range(1, N+1)} values..

dp 누적으로 최소값 구해줬습니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(N)] dp = [[[0,0,0] for _ in range(M)]] + [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N)] for i in range(1,N+1): for j in range(M): if j < M-1: dp[i][j][0] = min(dp[i-1][j+1][1],dp[i-1][j+1][2]) + matrix[i-1][j] if 0 <..