one Book a Day

투포인터를 각 출발선마다 돌리는 로직입니다. 정렬후 앞에서 하나씩 고정값으로 픽스시켜두고 두가지 포인터로 합의 범위를 0으로 수렴시켜나가는 과정입니다. import sys input = sys.stdin.readline n = int(input()) liquid = sorted(list(map(int, input().split()))) close_zero = float('inf') selected = [0]*3 for start in range(n - 2): left, right = start + 1, n - 1 while left < right: sum_value = abs(liquid[start] + liquid[left] + liquid[right]) if sum_value < close_zero:..

트리의 지름 문제. bfs 두번을 통해 최대 거리를 두번 산출해주면 된다. 조금 중요한게 graph배열을 1부터가 아니라 0부터 만들어 주어야 한다는점. (노드가 1개일때 내가 노드를 1로 설정해둬서.. 지금보니 그냥 target_node를 1로 설정해 주었다면 1부터 해도 될것같다) import sys input = sys.stdin.readline from collections import deque def bfs(start): q = deque() q.append((start, 0)) visited = [False for __ in range(10001)] visited[start] = True max_dist = 0 target_node = 0 while q: cur_node, cur_dist =..

확률을 인자로 넘기는 백트래킹. def dfs(row, p): global max_p if row == N: max_p = p return for col in range(N): next_p = p * P[row][col] if not col_check[col] and next_p > max_p: col_check[col] = True dfs(row + 1, next_p) col_check[col] = False for test in range(1, int(input()) + 1): N = int(input()) P = [list(map(lambda x: int(x) / 100, input().split())) for __ in range(N)] col_check = [False] * N max_p = 0..

숫자의 순서가 정해져 있으므로 greedy하게 풀면 된다. import sys input = sys.stdin.readline N , K = map(int,input().split()) nums = list(input().rstrip()) answer = [] for i in range(N): while K != 0 and answer: if answer[-1] < nums[i]: answer.pop() K -= 1 else: break answer.append(nums[i]) if K: answer = answer[:-K] print(''.join(answer))

책을 순서대로 쌓으므로 그디리하게 풀어야합니다. import sys input = sys.stdin.readline N, M = map(int, input().split()) weights = list(map(int, input().split())) box, cnt = M, 1 for weight in weights: if box - weight >= 0: box -= weight else: cnt += 1 box = M - weight if not N: cnt = 0 print(cnt)

순서대로 방문하는 문제같은 경우 플로이드 워셜을 많이 쓴다. 최초 1을 써놓고 플로이드 워셜을 통해 갈 수 있는 지점들을 하나하나 1로 바꾸어 주는 전략. import sys input = sys.stdin.readline n, k = map(int, input().split()) matrix = [[0] * n for __ in range(n)] for __ in range(k): a, b = map(lambda x : int(x) - 1, input().split()) matrix[a][b] = 1 for k in range(n): for i in range(n): for j in range(n): if matrix[i][k] and matrix[k][j]: matrix[i][j] = 1 for __..

기본적으로 문자열을 쌓거나 줄이는 방법은 dfs가 기본이다. 1번풀이 : 하나씩 쌓는 방법 left, right로 하나씩 쌓아가며 이어붙힌다. 다 붙히면 중복 없어지고 종료 import sys input = sys.stdin.readline def dfs(left, right, string): if len(string) == target: answers.add(string) return if left > 0: dfs(left - 1, right, string + N[left - 1:right + 1]) if right < n: dfs(left, right + 1, string + N[left: right + 2]) N = input().rstrip() n = len(N) target = n * (n + ..

일단 n을 무조건 수가 적은쪽으로 통일 시킨 후 dp로 각각 짝을 지어줬을 시 차이가 min인 값을 누적시킵니다. 앞인자는 수가 적은쪽의 인자고 뒤 인자는 수가 많은쪽의 인자입니다. m - (n - 1)은 수가 큰거에서 작은 것을 빼고 1을 더해준 값으로 선택할 수 있는 m쪽 인자의 index 범위를 뜻합니다. import sys input = sys.stdin.readline n, m = map(int, input().split()) boys = list(map(int, input().split())) girls = list(map(int, input().split())) if n > m: boys, girls = girls, boys n, m = m, n dp = [[0] * m for __ in r..

짝수 인덱스는 앞에서 부터 누적합을 구하고 홀수 인덱스는 뒤에서 부터 누적합을 구해서 밑장을 내가 가지는 경우와 상대를 주는 경우 두가지에 따라 최댓값을 갱신합니다. import sys input = sys.stdin.readline N = int(input()) x = list(map(int, input().split())) # 0, 2, 4 ... 밑장을 받거나 상대 주거나. 하고 홀수 idx를 받음. even_sum, odd_sum = [0] * (N // 2), [0] * (N // 2) even_sum[0], odd_sum[-1] = x[0], x[-1] for i in range(1, N // 2): even_sum[i] = x[2 * i] + even_sum[i - 1] odd_sum[-i ..

도착하는 경우의 수를 check 한다. 각 지점마다 2개의 분기로 나누어 지는걸 고려 dp로 누적시킨다. 이동가능 거리가 0이면 정지하므로 연산하지 않는다. import sys input = sys.stdin.readline N = int(input()) board = [list(map(int, input().split())) for _ in range(N)] dp = [[0] * N for _ in range(N)] dp[0][0] = 1 for row in range(N): for col in range(N): if not board[row][col]: continue jump = board[row][col] if col + jump < N: dp[row][col + jump] += dp[row][c..