흙금이네 블로그

아이디어 마감 시간 기준으로 정렬한 후 소요되는 시간을 빼면서 이전 마감 시간과 비교한다. 풀이 import sys input = sys.stdin.readline def solution(): N = int(input()) works = [tuple(map(int, input().split())) for _ in range(N)] works.sort(key=lambda x: -x[1]) res = works[0][1]-works[0][0] for i in range(1, N): if res > works[i][1]: res = works[i][1] res -= works[i][0] print(res if res >= 0 else -1) solution()

아이디어 데이크스트라 알고리즘으로 민준이가 마산으로 가는 최단 경로와 건우를 거쳐 마산으로 가는 최단 경로를 구한다. 풀이 import sys input = sys.stdin.readline INF = int(1e8) def solution(): def dijkstra(idx): D = [INF]*(V+1) D[idx] = 0 queue = [(idx, 0)] while queue: u, c = queue.pop(0) if D[u] c+_c: D[v] = c+_c queue.append((v, c+_c)) return D V, E, P = map(int, input().split()) graph = [[] for _ in..

아이디어 수를 문자열로 반복하여 10자리 이상으로 만든 값을 기준으로 수들을 내림차순 정렬한다. 풀이 def solution(): _ = int(input()) numbers = input().split() numbers.sort(key=lambda x: x*10, reverse=True) res = ''.join(numbers) if res[0] == '0': print(0) else: print(res) solution()

아이디어 선택 정렬처럼 교환할 원소를 찾고, 거품 정렬의 교환 방법처럼 원소를 교환하며 내림차순 정렬한다. 풀이 앞에서부터 차례로 교환할 수 있는 범위 내 가장 큰 수를 찾고, 해당 원소를 앞쪽으로 이동시킨다. def solution(): N = int(input()) A = list(map(int, input().split())) S = int(input()) cnt = S for i in range(N-1): max_val = A[i] max_idx = i for j in range(i+1, min(i+cnt+1, N)): if A[j] > max_val: max_val = A[j] max_idx = j if max_idx > i: for j in range(max_idx, i, -1): A[j-1]..

아이디어 0이 등장하려면 중앙값 이하의 수가 모두 1이 되어야 한다. 풀이 #1 2의 거듭제곱마다 연산 횟수가 늘어나므로 2를 거듭제곱하며 중앙값 이하의 수에 대해 연산 횟수를 더해 나간다. res는 중앙값 이하의 수가 모두 1이 되는 연산 횟수이므로 0이 등장하는 res+1을 출력한다. def solution(): N = int(input()) A = sorted(map(int, input().split())) res = cnt = 0 k = 2 for i in range((N+1)//2): while k-1 < A[i]: cnt += 1 k *= 2 res += cnt print(res+1) solution() 풀이 #2 연산 횟수는 2진수(비트)로 나타낸 수의 길이-1로 나타낼 수 있고, 비트 길이..

아이디어 정렬 후 스위핑으로 덮이지 않은 웅덩이를 덮기 위한 널빤지 최소 개수를 구해 나간다. 풀이 import sys input = sys.stdin.readline def solution(): N, L = map(int, input().split()) hole = sorted([tuple(map(int, input().split())) for _ in range(N)]) res = last = 0 for s, e in hole: if e > last: if last > s: s = last cnt = (e-s)//L if (e-s)%L: cnt += 1 last = s+L*cnt res += cnt print(res) solution()

아이디어 #1 이동거리 합이 최소가 되는 위치는 행과 열 번호 각각의 중앙값이므로, 각 번호와 중앙값과의 차를 모두 더한다. 풀이 #1 행과 열을 구분하여 입력 받은 번호들을 정렬한 후 각각의 중앙값을 찾아 계산한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) R, C = [], [] for _ in range(M): r, c = map(int, input().split()) R.append(r) C.append(c) R.sort() C.sort() res = 0 mr = R[M//2] mc = C[M//2] if M%2 == 0: mr = (mr+R[M//2-1])//2 mc = (mc+C[..

아이디어 백트래킹으로 현재 포함된 학생들 모두의 친구이면서 번호가 가장 작은 학생을 포함해 나간다. 풀이 import sys input = sys.stdin.readline def solution(): def dfs(idx, u, li, s): nonlocal res if idx >= K: if not res: res = li return if res: return for v in range(u+1, N+1): if visited[v] == 0: if v in s: visited[v] = 1 dfs(idx+1, v, li+[v], s&graph[v]) K, N, F = map(int, input().split()) graph = [set() for _ in range(N+1)] for _ in range..

아이디어 다익스트라로 최소 도로 건설 비용을 구해 나간다. 풀이 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e7) delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): m, n = map(int, input().split()) board = [tuple(map(int, input().split())) for _ in range(m)] D = [[INF]*n for _ in range(m)] heap = [] if board[0][0] != -1 and board[-1][-1] != -1: heap = [(board[0][0], 0, 0)] whi..

아이디어 1915번 가장 큰 직사각형 문제와 유사한 문제로, 동적 계획법으로 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다. 풀이 import sys input = sys.stdin.readline def solution(): M, N = map(int, input().split()) board = [tuple(map(int, input().split())) for _ in range(M)] dp = [[0]*(N+1) for _ in range(M+1)] L = 0 for i in range(M): temp = 0 for j in range(N): if board[i][j] == 0: dp[i+1][j+1] = dp[i][j+1]+1 if dp[i+1][j+1] > L: temp += 1 if ..