Algorithm475 [파이썬] 백준 23034 : 조별과제 멈춰 (플레5) [파이썬] 백준 23034 : 조별과제 멈춰 (플레5) 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 문제 풀이 0. 방향성 생각 2개의 집합으로 분리 + 최소비용으로 간선 잇기 = 크루스칼 두 간선 사이 연결 끊기 : a 노드부터 b 노드까지 간선 중 최대값을 끊으면 최소 비용으로 두 집합 분리 가능 a,b가 10000개 이상 주어지니, 시간초과 해결을 위해서 a와b 사이 최대값을 구하는 list를 만들어준다. 1. 입력 from collections import deque import sys i.. 2023. 12. 22. [파이썬] 백준 1944 : 복제 로봇 (골드1) [파이썬] 백준 1944 : 복제 로봇 (골드1) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 문제 풀이 0. 방향성 생각 읽어보면 모든 노드를 방문하는데 최소 비용을 쓴다. 각 노드에서 복제가 일어나서 각 노드별로 최단거리를 먼저 구해줘야함. 여기서 S=K라고 생각해도 좋다. 역할동일 이동 시 간선 비용이 같으니 BFS를 돌려서 각 노드별 거리를 구해준다. 모든 노드를 방문하면서, 간선 길이의 합이 최소가 되는 -> MST 문제임을 확인할 수 있다. 1. 입력 from co.. 2023. 12. 19. [파이썬] 백준 9328 : 열쇠 (골드1) [파이썬] 백준 9328 : 열쇠 (골드1) 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 풀이 0. 방향성 생각 BFS + 시뮬레이션 BFS를 돌리면서 열쇠를 먹은 경우, 현재 상태를 변화시킨다. 변화된 상태에서 BFS를 또 돌리고 반복한다. 핵심은 열쇠를 먹고나서 BFS를 돌렸는데 변화가 없는 경우 탐색이 끝난 것. visit 배열을 어떻게 구성할까 하다가, 문제 조건에서 A to Z까지 다 나와서 26개를 비트마스킹으로 하기에는 array 크기가 좀 큰편이라 다른 방법 생각. 위에 생각처럼 한 stage마다 .. 2023. 12. 19. [파이썬] 백준 13904 : 과제 (골드3) [파이썬] 백준 13904 : 과제 (골드3) 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 풀이 방향성 생각 뒤에서 부터 시작하기 전체코드 from collections import defaultdict as dd import heapq as hq import sys input = lambda : sys.stdin.readline().rstrip() table = dd(list) for _ in range(int(input())): d,p = map(int,input().split()) table[d].append(-p) info = sorted.. 2023. 12. 19. 이전 1 ··· 60 61 62 63 64 65 66 ··· 119 다음
