PS109 [Baekjoon-Python] 13904 : 과제 https://www.acmicpc.net/problem/13904 접근 1일에 마감일이 6일 남은 과제를 하지 않기 위해 마감일을 내림차순으로 정렬해서 마감일이 큰 것부터 점수를 구한다. 현재 날짜에 마감할 수 있는 과제까지 꺼낸다. 꺼낸 과제 중 점수가 가장 큰 과제를 구한다. 풀이 from sys import stdin from heapq import heappop, heappush n = int(stdin.readline()) task = [] for _ in range(n): d, w = map(int, stdin.readline().split()) heappush(task, (-d, w)) possible_task, score = [], 0 for day in range(-task[0][0],.. 2024. 1. 16. [Baekjoon-Python] 2212 : 센서 https://www.acmicpc.net/problem/2212 접근 센서를 오름차순 정렬한다. 센서 사이의 거리를 구한다. 거리를 내림차순 정렬해서 앞에서 k - 1개를 뺀 나머지의 합을 구한다. 풀이 from sys import stdin n, k = int(stdin.readline()), int(stdin.readline()) sensor = sorted(map(int, stdin.readline().split())) distance = sorted([sensor[i + 1] - sensor[i] for i in range(n - 1)], reverse=True) print(sum(distance[k - 1 :])) # (1) (1) k가 2이상일 때부터 센서 사이의 거리를 줄일 수 있기 때문에.. 2024. 1. 16. [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. 이전 1 ··· 6 7 8 9 10 11 다음
