전체글118 [Baekjoon-Python] 1202 : 보석 도둑 https://www.acmicpc.net/problem/1202 접근 보석과 가방을 무게순으로 정렬한다. 가방에 담을 수 있는 무게까지 보석을 꺼낸다. 꺼낸 보석 중 가격이 가장 높은 보석을 구한다. 풀이 from sys import stdin from heapq import heappop, heappush n, k = map(int, stdin.readline().split()) jewel = sorted( [tuple(map(int, stdin.readline().split())) for _ in range(n)], key=lambda x: x[0] ) c = sorted(int(stdin.readline()) for _ in range(k)) price = 0 prices = [] for bag .. 2024. 1. 16. [Baekjoon-Python] 12904 : A와 B https://www.acmicpc.net/problem/12904 접근 반대로 문자열 t를 연산하여 s가 되는지 확인한다. 두 연산 모두 문자열 마지막에 A 또는 B를 추가하기 때문에 t의 마지막 인덱스를 삭제한다. 삭제한 문자가 B면 t를 뒤집는다. 풀이 from sys import stdin s, t = list(stdin.readline().rstrip()), list(stdin.readline().rstrip()) while len(s) < len(t): last = t.pop() if last == "B": t = t[::-1] print(1 if s == t else 0) 2024. 1. 16. [Baekjoon-Python] 2437 : 저울 https://www.acmicpc.net/problem/2437 접근 저울추의 누적합을 구하면서 다음 저울추가 누적합보다 크면 더 이상 무게를 측정할 수 없다. 풀이 from sys import stdin n = int(stdin.readline()) scale = sorted(map(int, stdin.readline().split())) weight = 1 for i in range(n): if weight < scale[i]: break weight += scale[i] print(weight) 2024. 1. 16. [Baekjoon-Python] 1520 : 내리막길 https://www.acmicpc.net/problem/1520 접근 dfs 또는 bfs 탐색하여 높이가 더 낮은 경우만 이동한다. 중복 탐색을 방지하기 위해 지점에 방문한 횟수를 메모이제이션한다. 풀이1 - bfs from sys import stdin from heapq import heappop, heappush def bfs(): q = [] heappush(q, (-board[0][0], 0, 0)) # (1) while q: h, x, y = heappop(q) h *= -1 for i in range(4): nx = x + directions[i] ny = y + directions[3 - i] if nx = m or ny = n or h = m or.. 2024. 1. 16. [Baekjoon-Python] 2638 : 치즈 https://www.acmicpc.net/problem/2638 접근 bfs 탐색해서 공기와 접촉한 치즈를 찾는다. 탐색된 공기, 치즈는 방문 처리해서 중복 탐색을 방지한다. 공기와 접촉한 치즈 중 두 변 이상이 접촉한 치즈를 필터링한다. 필터링되지 않은 치즈는 다시 bfs 탐색하기 위해 방문 처리를 해제한다. 필터링된 치즈를 녹인다. 녹인 치즈부터 bfs 탐색하여 치즈가 없어질 때까지 반복한다. 풀이 from sys import stdin from collections import deque def bfs(q): cheese = [] while q: x, y = q.popleft() for i in range(4): nx = x + directions[i] ny = y + directions[3 - .. 2024. 1. 16. [Baekjoon-Python] 1613 : 역사 https://www.acmicpc.net/problem/1613 접근 a(전 관계) b(후 관계)가 있을 때 dfs 탐색하여 b의 후 관계로 있는 사건을 a의 후 관계로 압축한다. 풀이 from sys import stdin def dfs(start): if visited[start]: return visited[start] = True # (1) for end in graph[start]: dfs(end) event[start].add(end) event[start] |= event[end] # (2) n, k = map(int, stdin.readline().split()) graph = [[] for _ in range(n + 1)] for _ in range(k): a, b = map(int, .. 2024. 1. 16. [Baekjoon-Python] 2109 : 순회강연 https://www.acmicpc.net/problem/2109 접근 d를 기준으로 오름차순 정렬한다. 우선순위 큐에 p를 삽입하고 큐 사이즈가 d보다 크면 가장 작은 p를 삭제한다. 풀이 from sys import stdin from heapq import heappop, heappush n = int(stdin.readline()) univ = sorted( [tuple(map(int, stdin.readline().split())) for _ in range(n)], key=lambda x: x[1] ) ans = [] for pay, day in univ: heappush(ans, pay) if day < len(ans): heappop(ans) print(sum(ans)) 2024. 1. 15. [Baekjoon-Python] 1062 : 가르침 https://www.acmicpc.net/problem/1062 접근 비트마스크를 적용하기 위해 알파벳을 아스키코드 - 97로 치환한다. "anta", "tica"를 구성하는 a, c, i, n, t도 K개에 포함된다. 알파벳을 K개 조합해서 비트 연산으로 단어를 몇 개 읽을 수 있는지 계산한다. 풀이 from sys import stdin from itertools import combinations n, k = map(int, stdin.readline().split()) if k < 5: # (1) print(0) elif k == 26: # (2) print(n) else: k -= 5 # (3) no_learned = set() words = [] for _ in range(n): w = 0 .. 2024. 1. 15. [Baekjoon-Python] 1285 : 동전 뒤집기 https://www.acmicpc.net/problem/1285 접근 비트마스크를 적용하기 위해 H = 0, T = 1 이진수로 치환한다. 행 방향으로 뒤집을 수 있는 모든 경우의 수를 구한다. 열 방향으로 탐색하면서 T 개수가 많으면 뒤집는다. 풀이 from sys import stdin N = int(stdin.readline()) coins = [] reverse_coins = [] for _ in range(N): i = N - 1 bit = 0 for state in stdin.readline().rstrip(): if state == "T": # (1) bit += 1 2024. 1. 15. [Baekjoon-Python] 1948 : 임계경로 https://www.acmicpc.net/problem/1948 접근 위상 정렬 알고리즘을 사용해서 각 도시까지 도달하는 최대 시간을 구한다. 현재 간선이 다음 도시로 가는 최대 시간이라면 다음 도시에 현재 도시를 저장한다. 도착 도시부터 시작하여 저장된 도시의 간선을 탐색해서 간선의 개수를 구한다. 풀이 from sys import stdin from collections import deque def topological_sort(start): q = deque([(start, 0)]) while q: now, dist = q.popleft() for next, next_dist in graph[now].items(): in_degree[next] -= 1 cost = dist + next_dist.. 2024. 1. 15. 이전 1 ··· 7 8 9 10 11 12 다음
