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)

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

가중치가 있는 사방탐색. 흔한 문제들처럼 거리 가중치가 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])

사진틀을 dict로 관리 갯수 초과하면 하나 삭제 import sys input = sys.stdin.readline from collections import defaultdict N = int(input()) n = int(input()) nums = list(map(int, input().split())) count = defaultdict(int) for i in range(n): count[nums[i]] += 1 if len(count) > N: min_val = float('inf') for candidate in count: if candidate == nums[i]: continue if count[candidate] < min_val: min_val = count[candidate] t..

1등을 찾고 삭제한 그룹에서 1등을 찾으면 2등 그룹이 나온다. import sys input = sys.stdin.readline from collections import defaultdict while 1: N, M = map(int, input().split()) if not N and not M: break rankers = defaultdict(int) answer = [] max_cnt = 0 for _ in range(N): a = list(map(int, input().split())) for num in a: rankers[num] += 1 if rankers[num] > max_cnt: max_cnt = rankers[num] answer = [num] elif rankers[num]..

bfs로 승객을 찾고 bfs로 도착지로 이동하는 방식. 도착지 이동하면 oil 충전하고 탑승요청 삭제. 유의할 예외는 도착지점 or 시작지점이 다른 승객 위치랑 겹치는 경우도 고려해주어야한다. import sys input = sys.stdin.readline from collections import deque from heapq import heappush def go_target(start_x, start_y, start_oil): q = deque() q.append((start_x, start_y, start_oil)) visited = [[False] * N for __ in range(N)] visited[start_x][start_y] = True while q: for __ in rang..