one Book a Day

신장트리에서 마지막 하나의 간선을 그리는 방법으로 트리간 가중치가 존재하지 않기 때문에 간단한 union-find로 풀 수 있다. import sys input = sys.stdin.readline def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(a, b): a = find(a) b = find(b) if a < b: a, b = b, a parent[b] = a N = int(input()) parent = {i: i for i in range(1, N+1)} for _ in range(N-2): a, b = map(int, input().split()) union(a, b) pi..

암호를 찾으면 7자리씩 decoding하고 배열에 저장해 유효성 판단하고 값을 반환합니다. 따로 알고리즘이 필요한 문제는 아닙니다. for test in range(1, int(input()) + 1): N, M = map(int, input().split()) nums = {'0001101': 0, '0011001': 1, '0010011': 2, '0111101': 3, '0100011': 4, '0110001': 5, '0101111': 6, '0111011': 7, '0110111': 8, '0001011': 9} bits = [] for _ in range(N): a = input() idx = 0 if bits: continue while idx < M - 7: idx += 1 if a[idx..

set으로 관리. import sys input = sys.stdin.readline delta = ((1, 0), (0, -1), (-1, 0), (0, 1)) N = int(input()) curves = set() for _ in range(N): x, y, d, g = map(int, input().split()) # (x,y)시작, 처음 d방향으로 시작,(처음 선분하나로 시작) g 세대까지 진행.(1개추가, 2개추가, 4개 추가, 8개 추가.. 90도 회전시키며.) curves.add((x, y)) cur_dragon = [d] next_dragon = [d] for _ in range(g+1): for d in cur_dragon: nx, ny = x + delta[d][0], y + delt..

3자리수가 최대라 0, 1, 2자리수까지만 차수 비교해주면 됨. import sys input = sys.stdin.readline N = int(input()) answer = 0 for num in range(1, N + 1): if num < 100: answer += 1 else: digits = list(map(int, str(num))) if digits[0] - digits[1] == digits[1] - digits[2]: answer += 1 print(answer)

각 경우의 수를 check 해주면 된다. def check(player, num): if player[num] == 3: return True if num > 1 and player[num - 1] and player[num - 2]: return True if num < 9 and player[num + 1] and player[num + 2]: return True if num and not num==9 and player[num + 1] and player[num - 1]: return True return False for test in range(1, int(input()) + 1): nums = list(map(int, input().split())) a = {i: 0 for i in rang..

웰노운. 빨리 끝나는 순으로 정렬 후 시작점과 비교해주며 작업 할당(그리디) for test in range(1, int(input()) + 1): N = int(input()) works = [tuple(map(int, input().split())) for _ in range(N)] works.sort(key=lambda x: (x[1], x[0])) last_finish = 0 cnt = 0 for s, e in works: if s >= last_finish: last_finish = e cnt += 1 print(f'#{test} {cnt}')

요새 비슷한 문제 너무 많이 풀었다. 매칭문제. 투포인터로 매칭 for test in range(1, int(input()) + 1): N, M = map(int, input().split()) w = list(map(int, input().split())) t = list(map(int, input().split())) t.sort(reverse=True) w.sort(reverse=True) answer = 0 left = 0 for truck in t: while left < N and truck < w[left]: left += 1 if left == N: break answer += w[left] left += 1 print(f'#{test} {answer}')

마찬가지로 백트래킹 문제. def dfs(depth, cur_node, total): global min_sum if depth == N-1: min_sum = min(min_sum, total + matrix[cur_node][0]) 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, next_node, total + matrix[cur_node][next_node]) col_check[next_node] = False for test in range(1, int(input()) + 1): N = int(input())..

백트래킹문제. def dfs(x, y, total): global min_sum if total > min_sum: return if x == N - 1 and y == N - 1: min_sum = min(min_sum, total) return for dx, dy in delta: nx, ny = x + dx, y + dy if nx < N and ny < N: dfs(nx, ny, total + matrix[nx][ny]) for test in range(1, int(input()) + 1): N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] delta = ((1, 0), (0, 1)) min_sum = flo..

카카오 블라인드 1차 6번 효율성 문제. 구간 합을 이용해 갱신하는 방법으로 그때 아이디어만 얻어두었다가 드디어 해결했다. 양 끝에만 적어두고 dp로 누적값 배열을 만든 후 최종 배열은 원배열 + 변화량 배열의 합으로만 구하는 방법. 프로그래머스에 이번년도 문제 올라오면 다시 풀어보자. 사람들이 웰노운 웰노운 거리더니.. 여튼 좋은 방법론을 얻었다. import sys input = sys.stdin.readline N, M = map(int, input().split()) H = list(map(int, input().split())) save = [0] * (N+1) for _ in range(M): a, b, k = map(int, input().split()) save[a-1] += k save[..