one Book a Day

동일한 수가 나오는 경우를 대비했는데 1등코드보니 같은수는 안나오는 것 같다. 일단 counting한 후 set에 저장한 것에서 checking하며 각 조합의 수를 answer 에 더해줬다. import sys input = sys.stdin.readline from collections import defaultdict from itertools import combinations n = int(input()) arr = list(map(int, input().split())) x = int(input()) check = defaultdict(int) nums = set() for num in arr: check[num] += 1 nums.add(num) answer = 0 for num in nums..

꺽일때마다(극점) 사거나 팔아주면 된다. import sys input = sys.stdin.readline N, W = map(int, input().split( )) costs = [int(input()) for __ in range(N)] coin = 0 for i in range(1, N): if not coin: if costs[i - 1] costs[i]: W += coin * costs[i - 1] coin = 0 if coin: W += coin * costs[N - 1] print(W)

겹치지않으면서 최소 집합과 최대집합의 차이가 최소가 되려면 공차가 1인 등차수열을 이뤄야함. 수열을 제외한 나머지는 K로 나누어 떻어져야 최소. import sys input = sys.stdin.readline N, K = map(int, input().split()) min_gap = K * (K + 1) // 2 if min_gap > N: print(-1) exit() answer = K - 1 if not (N - min_gap) % K else K print(answer)

후보군을 구하고 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..