one Book a Day

후보군을 구하고 knapsack import sys input = sys.stdin.readline N = int(input()) nums = [] num = 0 idx = 1 while num i: break dp[i] = min(dp[i], 1 + dp[i - num]) print(dp[N])

평범한 위상정렬 import sys input = sys.stdin.readline from collections import deque def topological_sort(): visited = {i: False for i in range(1, N + 1)} q = deque() for node in levels: if not levels[node]: q.append(node) visited[node] = True while q: cur_node = q.popleft() for next_node in next_nodes[cur_node]: levels[next_node] -= 1 if not visited[next_node] and not levels[next_node]: visited[next_no..

제한된 선택지에서 선택하는 문제는 dp로 접근하자 import sys input = sys.stdin.readline dp = [[1 if j==0 else i if j==1 else 0 for i in range(2001)] for j in range(15)] # j가 0일때 1이고 아니면 i인데 j가 1일때 i 고 아니면 0이다. for i in range(2,15): for j in range(1,2001): dp[i][j] = dp[i-1][j//2] + dp[i][j-1] for _ in range(int(input())): n,m = map(int,input().split()) sys.stdout.write(str(dp[n][m]) +'\n')

가중치가 있는 사방탐색. 흔한 문제들처럼 거리 가중치가 1인 경로를 찾는 것이 아닌 벽을 만나는 갯수를 가중치가 있는간선, 없는 간선으로 두어 우선처리해주어야 한다. heap을 쓰는 다익스트라, deque의 appendleft를 쓰는 dfs 두가지 방법이 있다. import sys input = sys.stdin.readline from heapq import heappush, heappop def dijkstra(): heap = [] heappush(heap, [0, 0, 0]) visited[0][0] = 1 while heap: cost, x, y = heappop(heap) if x == n - 1 and y == n - 1: return cost for i in range(4): nx = x ..

기본적인 0, 1배낭문제. 열은 hp, 행은 각 선택지. 이전 hp에서 최댓값을 계승할 것이냐? 아니면 새로운 선택지를 취할것이냐? import sys input = sys.stdin.readline N = int(input()) L = [0] + list(map(int, input().split())) P = [0] + list(map(int, input().split())) dp = [[0] * 101 for _ in range(N+1)] for i in range(1, N+1): for j in range(1, 101): if L[i]

책 판매량 저장하고 내림차순, 사전순 정렬 import sys input = sys.stdin.readline from collections import defaultdict N = int(input()) sell = defaultdict(int) for __ in range(N): book = input().rstrip() sell[book] += 1 arr_for_sort = [] for book in sell: arr_for_sort.append((sell[book], str(book))) arr_for_sort.sort(key=lambda x: (-x[0], x[1])) print(arr_for_sort[0][1])

싸이클을 지나는 경로에 속한 노드들에 대해 처리하는 문제입니다. 아직 scc에 대해 익숙하지 못해 TLE상태입니다. 현 로직은 dfs를 통해 방문 횟수를 check해 0, 1, 2상태에 대해서 처리 한 후 cycle에 속한 요소를 찾았다면 각 요소들에 대해 dfs로 순회해주며 이미 -1 처리되었다면 return하는 백트래킹까지 해주었습니다. 아직 7번째 test set에서 TLE상태라 조금 더 보완하겠습니다. import sys input = sys.stdin.readline # 1부터 탐색. cycle생기면 cycle에 포함되는 요소 하나 check. def dfs(cur_node, path): if answer[cur_node] < 2: answer[cur_node] += 1 for next_node..

실패한 코드입니다. 최초는 규칙대로 gcd를 모두 구해가며 진행했으나 TLE가 납니다. 때문에 소인수분해를 해서 각 요소를 제거해가며 풀이하려 했으나 아직 로직이 완벽하지 못합니다. 추후 보완하겠습니다. import sys input = sys.stdin.readline from collections import defaultdict for test in range(int(input())): n = int(input()) a = list(map(int, input().split())) cnt = 0 primes = defaultdict(int) for i in range(n): tmp = a[i] for j in range(2, tmp + 1): if tmp == 1: break if not tmp % ..

문제의 핵심은 결국 에어컨으로부터 얼만큼의 거리에 있는가? 입니다. 백준의 최대 직사각형 만들기, SWEA의 수영장 가자 와 동일한 문제로 dp를 이용해 방해물이 없으면 기존값에서 거리값을 늘려가며 기록해주되 방해물(나보다 작은 온도의 에어컨)이 나타나면 그값에서 부터 다시 거리값을 기록해줍니다. 본 풀이는 좌, 우 다른 dp를 사용했으나 경험상 dp하나로도 구현할 수 있습니다. import sys input = sys.stdin.readline for test in range(int(input())): input() n, k = map(int, input().split()) a = list(map(lambda x: int(x) - 1, input().split())) t = list(map(int, i..

앞전의 이진수에서 1이 있는 자릿수를 계승하는 수열을 growing sequence라 하고 그렇지 않은 수열을 xor연산을 통해 growing sequence로 만들어 주는 수열을 Co-growing Sequence라 합니다. 전에 있는 값을 pivot으로 가져가야할 1의 위치를 저장하는 기준값으로 정하고 pivot에는 1이 있는데 현 수열의 값에는 없다면 Co-growing Sequence가 그만큼의 값을 가져가게끔 코드를 짰습니다. import sys input = sys.stdin.readline for test in range(int(input())): n = int(input()) x = list(map(int, input().split())) pivot = x[0] y = [0] * n for..