one Book a Day

무너가 탐색을 해야할 것 같지만 사실 치킨집을 골라 모든 집까지의 거리들 중 최솟값들만 더해서 거리합을 갱신해준다. import sys input = sys.stdin.readline from itertools import combinations # 맵크기(N), 치킨집 최대 선택가능개수(M) N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] # 빈칸(0), 집(1), 치킨집(2) // 그래프 그리기. house = [] chicken = [] for i in range(N): for j in range(N): if board[i][j] == 1: house.append((i, j)) el..

union find의 변형. 특이한 점은 합칠때 부모가 아닌 해당 노드끼리 합치고 대신 해당 노드를 타고 올라가며 length를 갱신해줘야 된다는 점이다. 내 길이 = 부모의 길이들의 합. import sys input = sys.stdin.readline def find(x): if parent[x]==x: return x # 부모쪽 length모두 갱신 tmp = find(parent[x]) # 내 length 갱신 length[x] += length[parent[x]] # 부모값 저장 parent[x] = tmp # 반환. return tmp def union(a,b): length[a] = abs(a-b) % 1000 parent[a] = b for test in range(1,int(input(..

완전탐색을 하며 탐색한 값을 배열에 넣어 중복된 값을 탐색하지 않도록 해 최고 값을 저장해주는 방식. import sys input = sys.stdin.readline # 좌, 하, 우, 상 dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] def BFS(x, y): global answer q = set([(x, y, board[x][y])]) while q: x, y, ans = q.pop() # 좌우상하 갈 수 있는지 살펴본다 for i in range(4): nx = x + dx[i] ny = y + dy[i] # index 벗어나지 않는지 체크하고, 새로운 칸이 중복되는 알파벳인지 체크한다 if ((0

아이디어는 결국 2와 1을 같은 횟수 사용해야 된다는 것. 각 나무당 1을 필수적으로 써야할 횟수를 분리시킨다음 2를써야하는 횟수와 1을 써야하는 횟수의 차이(only 2만 있으면 해결 되는 수가 3의 배수고 2를써야하는 횟수가 더 많다면 2를 써야하는 횟수는 1과 2로 나눌 수 있으므로 가능하다. import sys input = sys.stdin.readline N = int(input()) h = list(map(int,input().split())) two = 0 one = 0 for wood in h: two += wood//2 one += wood%2 if not (two-one)%3 and two >= one: print('YES') else: print('NO')

전에 풀었던 행렬곱셈 문제와 동일한 로직이다. 문제의 핵심(dp누적의 핵심)은 이전 누적합이 새로운 누적합에 계속 중첩된다는 것. 때문에 i에서 j로 가는 모든 부분합에 대해 최솟값을 찾아 누적합값을 더해줘야 한다. 약간 예전에 처벌받은 벌에 대해 전과 괴심죄로 가중처벌 받는 느낌? 복리로 늘어나는 느낌? 그런 느낌의 수열. 대각선으로 덧셈을 진행(N*N인접행렬로 진행되며 중앙에서 멀수록 길이가 긴 행렬이며 합을 구할 때는 i에서 j까지의 중간 경유점k에 대해 분리해 2개의 합을 이루는 경우의 수를 모두 조사해준다. import sys input = sys.stdin.readline def solve(): N, A = int(input()), [0] + list(map(int, input().split(..

크누스 최적화(Knuth's optimization) 특수한 DP 점화식에 대해 적용할 수 있는 최적화. 조건 어떤 2차원 배열 C DP를 사용하는 2차원 배열 dp C는 i부터 j까지 합치는데 드는 비용. 여기서 비용은 이전 비용에 현재 비용을 누적해서 계산하는 문제이다. quadrangle inequeality : 사각부등식으로 (a,b,c) + (b,c,d)

LCA 기본형이다. LCA를 찾아 좌표를 반환하면 되는 문제 import sys sys.setrecursion(int(1e5)) input = sys.stdin.readline LOG = 21 # (1000000의 log2를 취한 값의 올림값)(2의 i승 단위의 부모값을 저장하기 위한 크기.) # 각 노드의 depth를 찾아 기록하기 위한 dfs def find_depth(cur_node, depth): check[cur_node] = True depth[cur_node] = depth for next_node in graph[x]: if not check[next_node]: parent[next_node][0] = cur_node find_depth(next_node, depth+1) # 공통조상 찾..

LCA 기본 형에 dists배열만 만들어주어 루트노드에서 각 정점까지의 거리를 저장해준 구조이다. dfs를 이용해 각 노드 본인의 depth를 기록함과 동시에 top-down으로 거리도 dp_dists에 기록한다. (여기까지의 거리 = 부모노드까지의 거리 + cost값이다.) 그럼 dists와 depth는 끝. sparse table을 통해 각 노드에서 2의 0승,1승,2승 위의 부모노드 번호에 대해 수집한다. LCA함수를 통해 2의 n승 단위로 부모를 빠르게 타고 올라가며 공통조상의 위치를 찾는다. 공통조상만 알면 거리 배열의 연산을 통해 각 정점 간 거리를 구할 수 있다. # 정점들 사이의 최단거리는 dist[a] - dist[lca] + dist[b] - dist[lca] # LCA를 지나는 거리가..

LCA(lowest common ancestor)최소 공통 조상 모든 노드에 대한 깊이(depth)를 계산합니다. LCA를 찾을 두 노드를 확인합니다. depth가 동일하도록 거슬러 올라갑니다. 이후 부모가 같아질때까지 반복적으로 두 노드의 depth를 낮춥니다. 모든 LCA(a,b)연산에 대해 2번의 과정을 반복합니다. 느린 탐색 import sys sys.setrecursion(int(1e5)) # 각 노드의 depth를 찾아 기록하기 위한 dfs def find_depth(cur_node, depth): check[cur_node] = True depth[cur_node] = depth for next_node in graph[x]: if not check[next_node]: parent[next..

조합의 수를 구하는 가장 빠른 방법은 아래 구현한 함수를 이용하는 것이다.(반복문이 가장 빠름) 간선의 모양? 하나에서 다음 하나를 더하는 식으로 구하면 경우의 수를 모두 구할 수 있지 않을까? 에 대한 생각. 결국 ㄷ자와 ㅈ자에 대해 구한다면 5개를잇는 간선은 ㄷ와 ㅈ에서 각 하나씩 더하는 방법이 있겠다. import sys read = sys.stdin.readline # 조합을 팩토리얼로 구함(a~(a-b+1))까지 곱한값 분자 1~b까지 곱한값 분모. def set_combination_cnt(a, b): com_cnt = 1 if a-b < b: b = a-b for i in range(a-b+1, a+1): com_cnt *= i for j in range(1, b+1): com_cnt //=..