1.풀이 (1) 주어진 선후관계만으로 q와 graph를 구성한다 (2) q에 있는 요소 중 가장 작은(가장 쉬운)것을 pop하면서 진행한다 => heap을 쓴다. ​ * 두가지풀이 - 소스코드1(시간초과) : toNode와 fromNode를 사용. fromNode를 하나씩 삭제하고 fromNode가 비어있을때 pq에 넣음 - 소스코드2 (통과) : toNode와 들어오는 노드의 개수(cntParent)를 사용. cntParent 0이 될때 pq에 넣음 ​ 2. 소스코드 (1) 소스코드1 (python3 시간초과) import heapq N,M=map(int,input().split()) fromNode={} toNode={} for i in range(1,N+1): fromNode[i]=[] toNode..

1. 풀이 모든 문제는 푸는데 1시간이 걸리기 때문에, 컵라면을 가장 많이주는걸 그리디하게 고르면 된다. 이때 문제마다 데드라인이 다르기 때문에 시간을 뒤에서부터 1시간 단위로 탐색하면서 먼저 끝나는 일 중에 컵라면을 많이 주는 것부터 차례대로 수행하면 된다. 2. 소스코드 from collections import deque import heapq N=int(input()) L=[] for i in range(N): L.append(list(map(int,input().split()))) # t시간까지 해야되는거 pq에추가 def addPQ(t): while(L): dead,cup=L.pop() if dead==t: heapq.heappush(cupPQ,-1*cup) else: L.append([dea..

1. 풀이 (1) 주유소의 위치를 기준으로 가까운 순으로 정렬을 한다. (2) 현재위치에서 최대로 갈 수 있는 위치를 확인한다 - 갈 수 있는 위치가 도착지점을 넘으면 -> 종료 - 넘지 않으면 -> 갈 수 있는 위치까지의 주유소 중 가장 주유를 많이 할 수 있는 곳에서 주유 (3) 주유한 만큼 위치이동 (4) (2),(3)을 반복 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...

1.풀이 (1) 2개의 연결된 그래프를 만들기 위해선 크루스칼 알고리즘을 적용한 뒤 가장 큰 간선을 하나 빼면된다. 이때 가장 큰 간선은 N-1번째에 들어오는 간선이므로, 2개의 mst를 만들기 위해선 간선을 N-2번째까지 추가해 주면 된다. (2) 최소간선부터 하나씩 넣어볼 때, pq를 쓰는방법과 sort를 하고 앞에서부터 뽑는 방법이 있다. 결과는 아래와 같다. 소스코드1 : edge.pop(0)을 해줌 ->시간초과 소스코드2 : edge[i]로 참조해줌 -> 통과 (5696ms) 소스코드3 : heapq.heappop() -> 통과 (6992ms) *pq는 매번 pop하고 정렬해주어야 하기 때문에 한번 정렬 후 앞에서 부터 참조하면 되는 소트보다 느림 단, 소트후 앞에서..

1. 풀이 (1) 현재 가지고 있는 기름으로 방문가능한 모든 주유소 중에 가장 기름을 많이 넣을 수 있는 주유소를 후보에 추가한다. (이때 후보주유소는 힙으로 관리한다. 게속 추가하고 매회 최댓값을 추출해야 하기 때문) (2) 후보(heap)에서 최댓값을 추출한다. (이때 방문횟수를 +1) * 만약 방문할 주유소가 없으면 답은 -1 2. 소스코드 import heapq import sys from collections import deque N=int(input()) point=[] for i in range(N): a,b=map(int,sys.stdin.readline().rstrip().split()) point.append([a,b]) L,P=map(int,input().split()) point...