one Book a Day

책을 순서대로 쌓으므로 그디리하게 풀어야합니다. 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..

끝에서부터 1나오면 뒤집어주면 됩니다. import sys input = sys.stdin.readline def xor(a, b): for row in range(a + 1): for col in range(b + 1): matrix[row][col] ^= 1 n, m = map(int, input().split()) matrix = [list(map(int, list(input().rstrip()))) for __ in range(n)] cnt = 0 for row in range(n - 1, -1, -1): for col in range(m - 1, -1, -1): if matrix[row][col]: cnt += 1 xor(row, col) print(cnt)

3개 -> 2개 -> 1개 각 지점마다 살수있는 만큼 사주면 된다. 주의할 점은 두번째 지점의 갯수가 세번째보다 큰경우. 이경우는 2개씩 사는 과정을 먼저 해주어야한다. import sys input = sys.stdin.readline def buy_triple(idx): global cost k = min(arr[idx: idx + 3]) arr[idx] -= k arr[idx + 1] -= k arr[idx + 2] -= k cost += 7 * k def buy_double(idx): global cost k = min(arr[idx: idx + 2]) arr[idx] -= k arr[idx + 1] -= k cost += 5 * k def buy_each(idx): global cost cost..

그리디 문제. 3개를 동시에 살수있는 만큼 사고 2개를 사고 1개를 사는 방법. 주의할 점은 두번째 지점의 갯수가 세번째보다 큰경우. 이경우는 2개씩 사는 과정을 먼저 해주어야한다. import sys input = sys.stdin.readline def buy_triple(idx): global cost k = min(arr[idx: idx + 3]) arr[idx] -= k arr[idx + 1] -= k arr[idx + 2] -= k cost += (B + 2 * C) * k def buy_double(idx): global cost k = min(arr[idx: idx + 2]) arr[idx] -= k arr[idx + 1] -= k cost += (B + C) * k def buy_each..

궁수를 전진시키며 bfs로 target을 찾는 방식. 모든 적을 없앴는데 탐색하는 경우만 가지치기 해주면 조금 더 빠른 로직을 짤 수 있을 것 같다. 하지만 지금코드도 충분히 직관적이고 깔끔하기 때문에 마무리. import sys input = sys.stdin.readline from collections import deque from heapq import heappush def search_target(x, y): if enemies[x][y]: return (x, y) q = deque() q.append((x, y)) visited = [[False] * M for __ in range(N)] visited[x][y] = True target_candidate = [] for __ in ran..