one Book a Day

오랜만에 푸는 LCS(substring), string과 편집거리도 같이 연습했습니다. import sys input = sys.stdin.readline a, b = input().strip(), input().strip() n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n): for j in range(m): dp[i + 1][j + 1] = dp[i][j] + 1 if a[i] == b[j] else max(dp[i + 1][j], dp[i][j + 1]) print(dp[-1][-1])

그리디하게 맨 뒷 자리가 짝수면 2로 나누고 1이면 1빼면 된다. import sys input = sys.stdin.readline A, B = map(int, input().split()) cnt = 1 while A != B: if A > B or (B % 10 != 1 and B % 2 != 0): cnt = -1 break if B & 1: B //= 10 cnt += 1 else: B //= 2 cnt += 1 print(cnt)

import sys input = sys.stdin.readline N = int(input()) costs = [list(map(int, input().split())) for _ in range(N)] costs.sort() dp = [0] * N max_profit = 0 answers = [] for i in range(N): for j in range(i, N): tmp = costs[i][0] - costs[j][1] if tmp > 0: dp[i] += tmp if max_profit

기본적인 bfs문제입니다. import sys input = sys.stdin.readline from collections import deque def bfs(i, j): q = deque() q.append([i, j]) max_n = 0 while q: a, b = q.popleft() for k in range(4): x = a + dx[k] y = b + dy[k] if 0

결과를 누적시켜주며 끝까지 간다 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) dp = arr[:] for i in range(N): for j in range(i): if arr[j] > arr[i]: dp[i] = max(dp[i], dp[j] + arr[i]) print(max(dp))

몇단 고음까지 올라가냐? 좀 문제가 직관성이 떨어지지만 그냥 target을 올려가면서 hit하면 올려주면 된다. n, a, d = map(int,input().split()) L = list(map(int,input().split())) check = 0 for pt in range(n): if L[pt] == a: check += 1 a += d print(check)

내림차순 정렬 후 3번째 물건은 공짜로 계산하면 됩니다. import sys input = sys.stdin.readline n = int(input()) nums=sorted([int(input()) for _ in range(n)], reverse=True) answer = 0 for i in range(n): if not i % 3 == 2 : answer += nums[i] print(answer)

B가 오름차순이므로 이분탐색 upperbound로 내가 들어갈 자리 찾는다. import sys input = sys.stdin.readline from bisect import bisect_right N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) answer = [] for idx, a in enumerate(A): answer.append(bisect_right(B, a) - idx - 1) print(*answer)

물고기 움직이고 상어 움직이면 된다. import sys input = sys.stdin.readline def move_fish(arr): ret = [[[] for _ in range(4)] for _ in range(4)] for x in range(4): for y in range(4): while arr[x][y]: d = arr[x][y].pop() for i in range(d, d - 8, -1): i %= 8 nx, ny = x + delta[i][0], y + delta[i][1] if (nx, ny) != shark and 0

유명한 소수 판별 테크닉. 2부터 int(N**0.5) + 1까지의 배수를 기존 집합에서 제외시키는 로직 N, K = map(int, input().split()) cnt = 0 nums = [True] * (N + 1) for i in range(2, int(N**0.5) + 1): for j in range(i, N+1, i): if nums[j] == True: nums[j] = False cnt = cnt + 1 if cnt == K: print(j) break