one Book a Day

hashmap에 tuple로 조합수를 구하는 것까지는 접근했는데 set으로 압축시키는 것은 생각을 못했음. 이러면 결국 tuple에 각 순위값이 들어가게 되는데 동일한 요소의 경우 묶여서 사라지기때문에 순위값의 갯수가 적어져 일일히 비교할 필요가 없어짐. 정렬과 indexing을 같이 사용해서 크기 비교를 해야할 때 유용하게 쓸 수 있을 것으로 보임 import sys input = sys.stdin.readline from collections import defaultdict m, n = map(int, input().split()) universe = defaultdict(int) for _ in range(m): planets = list(map(int, input().split())) keys ..

시작정점을 어디로 두어야 하는가? 초기 최단거리값을 float('inf)가 아닌 정수로 두어야 하는 이유가 무엇인가? 두가지에 대해 고민해볼 필요가 있는 문제 두 가지 조건에 따라 시작 지점에서 도달 할 수 있는 또는 도달할 수 없는 음수 사이클 판별 가부가 결정된다. import sys input = sys.stdin.readline def bellman_ford(start): dists[start] = 0 for cycle in range(n): for cur_node, next_node, cost in edges: if dists[cur_node] + cost < dists[next_node]: dists[next_node] = dists[cur_node] + cost if cycle == n - ..

시간초과가 나오는 code이다. import sys input = sys.stdin.readline from bisect import bisect_right from math import factorial MOD = int(1e9) + 7 for test in range(int(input())): n, m, k = map(int, input().split()) arr = list(map(int, input().split())) arr.sort() done = {} answer = 0 for i in range(n - m + 1): if arr[i] not in done: right = bisect_right(arr, arr[i] + k) done[arr[i]] = right length = done[ar..

이거 cycle을 산출하는 공식이 이해가 안됨. 이번주 내로 해결할 예정 import sys input = sys.stdin.readline from bisect import bisect_left # 풀이 참고했는데 for test in range(int(input())): n, m = map(int, input().split()) arr = list(map(int, input().split())) prefix_sum, idxes, idx, total = [], [], 0, 0 for num in arr: total += num if not prefix_sum or prefix_sum[-1] < total: prefix_sum.append(total) idxes.append(idx) idx += 1 x ..

좀 무식하게 푼 느낌이 없잖아 있습니다. 달팽이 거꾸로 파고들면서 그렸습니다. 빈칸은 -1로 표기 빈칸 없을때와 빈칸이 있을 떄 1열로 펼치는 순서가 다릅니다. import sys input = sys.stdin.readline from collections import deque # 달팽이를 만든다. 시작좌표는 def make_snail(): row, col = n, n if n**2 - N >= n: col -= 1 matrix = [[0] * col for _ in range(row)] q = deque() q.append((row - 1, col - 1, 0)) blank_cnt = row * col - N start = N - 1 while q: x, y, d = q.popleft() matri..

실상 온풍기를 돌리고 영역의 온도를 확산시키고 그런것들은 어렵지 않았으나 벽에 대한 분기의 처리가 조금 까다로웠다. 바람 방향에 따라 갈수없는 영역이 정해진다. 갈 수 없는 영역 정보에 대해선 key-value로 접근하도록 해 check하고 초콜릿 101개 이상 못먹는다는 문장을 못봐서 3시간정도 낭비한듯.. 그거 한문장이 안보여서 K가 1000인데 어떻게 101분기만에 목표를 달성하는지 말이 안된다고 생각했다.. from collections import defaultdict, deque import sys input = sys.stdin.readline def spread_temperature(): for warmer in warmers: q = deque() x, y = warmer d = warm..

등차수열로 속도가 증가했을 때 k번째 돌에서 a만큼의 최대 속도를 가질 수 있고 이는 k = a(a+1)/2 를 만족한다. 정리하면 a = sqrt(2 * k + (1/4)) - 1/2 이기 때문에 i번 위치에서 int(sqrt(2 * i)) + 1까지 검사하면 가능한 모든 속도에서의 값을 조사할 수 있다. import sys input = sys.stdin.readline N, M = map(int, input().split()) dp = [[float('inf')] * (int((2 * N)** 0.5) + 2) for _ in range(N + 1)] dp[1][0] = 0 stones = set([int(input()) for _ in range(M)]) for i in range(2, N + 1..

풀이 1. 극소점부터 큰값이 나올때마다 그만큼 채워주면서 연산. import sys input = sys.stdin.readline n = int(input()) cnt = 0 stack = [int(input())] max_num = stack[-1] for _ in range(n - 1): num = int(input()) if stack[-1] < num: cnt += num - stack[-1] max_num = max(max_num, num) stack.pop() stack.append(num) cnt += max_num * len(stack) - sum(stack) print(cnt) 풀이2. 분할정복으로 max_idx를 pivot으로 좌우 분할 해 각 구간의 연산값을 더해주며 최상단까지 올라..

재귀 dp로 안쪽에서부터 경우의 수를 뽑아오며 밖으로까지 cnt 값을 누적시켜 꺼내왔습니다. import sys input = sys.stdin.readline ans = list(map(int, input().split())) dp = [[[[-1 for score in range(11)] for pre2 in range(6)] for pre in range(6)] for depth in range(11)] def make_dp(depth, pre, pre2, score): if dp[depth][pre][pre2][score] != -1: return dp[depth][pre][pre2][score] if depth == 10: return 1 if score >= 5 else 0 cnt = 0 fo..

각 value, cnt를 축으로 둔 2차원 dp를 통해 하나씩 고르는 경우의 수를 check해주었습니다. 이전에 수확한게 왼쪽인지 오른쪽인지 각각 수확량의 최댓값을 취하며 계산해 주었습니다. import sys input = sys.stdin.readline N = int(input()) v = [0]+[int(input()) for _ in range(N)] dp = [[v[i] * N if i == j else 0 for i in range(N + 1)] for j in range(N + 1)] for left in range(1, N + 1): for right in range(left - 1, 0, -1): dp[right][left] = max(dp[right + 1][left] + v[righ..