one Book a Day

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

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 <..

평범한 조합문제입니다. 대신 조건에 만족하는 조합에서 return을 주면 그 후에 다른 수를 취하더라도 조건에 맞을 수 있는 경우가 걸러지기 때문에 return을 하면 안됩니다. import sys input = sys.stdin.readline def dfs(idx, s, min_n, max_n): global cnt if L R: return for next_idx in range(idx+1,N): dfs(next_idx, s+arr[next_idx], min(min_n, arr[next_idx]), max(max_n, arr[next_idx])) N, L, R, X = map(int, input().split()) arr = list(map(int, input().split())) cnt = 0 d..

후위표기식은 늘 stack을 사용하여 풀이한다. a = input() stack = [] #스택 res='' #출력 for x in a: if x.isalpha(): #피연산자인지 아닌지 확인 res+=x else: if x == '(': stack.append(x) elif x == '*' or x =='/': while stack and (stack[-1]=='*' or stack[-1]=='/'): res+=stack.pop() stack.append(x) elif x == '+' or x == '-': while stack and stack[-1] != '(': res += stack.pop() stack.append(x) elif x == ')': while stack and stack[-1] ..

간단한 bfs문제 import sys input = sys.stdin.readline from collections import deque def bfs(i,j): q = deque() q.append((i,j)) visited[i][j] = 1 while q: x, y = q.popleft() for d in delta: nx, ny = x + d[0], y + d[1] if 0

실수하면 0점 실수 안하면 1점을 부여 총 곡의 갯수 - 총 점수로 실수한 갯수를 계산. import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) dp = [0]*N for i in range(1,N): if arr[i-1]

사이의 중간값 or 양끝까지의 값 중 가장 큰 값. import sys input = sys.stdin.readline N = int(input()) M = int(input()) arr = list(map(int, input().split())) max_size = 0 for i in range(1,M): max_size = max(max_size, arr[i] - arr[i-1]) print(max((max_size+1)//2,arr[0] - 0, N - arr[-1]))

1. dfs를 통해 각 cctv의 방향에 따른 조합을 구합니다. 2. 조합으로 만들어진 cctv_set을 통해 색칠하는 식으로 감시영역을 구합니다. import sys input = sys.stdin.readline def check_zero_area(cctvs): tmp = [[1]*M for _ in range(N)] q = [] for cctv in cctvs: init_x, init_y, cctv_id, cctv_dir = cctv tmp[init_x][init_y] = 0 dirs = cctv_setting[cctv_id][cctv_dir] for d in dirs: q.append((init_x, init_y)) while q: x, y = q.pop() nx = x + delta[d][0] ..

구현을 처음풀때는 막막했지만 브루트포스에 대해 알고난 이후로 어렵게 느껴지지는 않는 문제. 이제는 왜 골드5인줄 알겠다. 벽을 어떻게 고를 것인가? 여유공간은 어떻게 산출할 것인가? import sys input = sys.stdin.readline from itertools import combinations from collections import deque def bfs(walls): q = deque() visited = [[False]*M for _ in range(N)] ret = 0 for wall in walls: i, j = wall lab[i][j] = 1 for v in virus: x, y = v q.append((x,y)) visited[x][y] = True while q: x..