one Book a Day

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..

union- find를 통해 집합을 나누고 group의 크기를 측정해 출력해줬습니다. def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N, M = map(int, input().split()) prefer_set = list(map(int, input().split())) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, ..

백준의 유명한 bfs 시리즈인 숨바꼭질 시리즈의 일종. 쓸데없는 visited 배열 할당을 없애기위해 set으로 관리했는데 나쁘지 않은 것 같다. from collections import deque def bfs(start): q = deque() q.append((start, 0)) visited = set() visited.add(start) while q: cur_node, cnt = q.popleft() for next_node in (cur_node + 1, cur_node - 1, cur_node * 2, cur_node - 10): if next_node

최소 배열 합 문제와 완전히 동일한 백트래킹 문제입니다. def dfs(depth, total): global min_sum if depth == N: min_sum = min(min_sum, total) return if total > min_sum: return for next_node in range(N): if not col_check[next_node]: col_check[next_node] = True dfs(depth + 1, total + matrix[depth][next_node]) col_check[next_node] = False for test in range(1, int(input()) + 1): N = int(input()) matrix = [list(map(int, input(..

dp로 뒤에서부터 최솟값을 가져와 0까지 역산했습니다. for test in range(1, int(input()) + 1): N, *battery = map(int, input().split()) dp = [float('inf')] * N dp[N - 1] = 0 for i in range(N - 1, -1, -1): for j in range(i - 1, -1, -1): if j + battery[j] >= i: dp[j] = min(dp[j], dp[i] + 1) print(f'#{test} {dp[0] - 1}')

궁수를 전진시키며 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..

동일한 수가 나오는 경우를 대비했는데 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)