링크 : https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 코드 import sys input = sys.stdin.readline import heapq def dijkstra(start): Q = [] heapq.heappush(Q,(0,start)) dist = [1e9] * (n + 1) dist[start] = 0 while Q: total, node = heapq.heappop(Q) if dist[node..

링크 : https://www.acmicpc.net/problem/13308 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 코드 import heapq,sys input=sys.stdin.readline n,m = map(int,input().split()) price = [0]+list(map(int,input().split())) graph = [[] for _ in range(n + 1)] for _ in range(m): a,b,w = map(int,input().split()..

링크 : https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 코드 import sys input = sys.stdin.readline def find(node): if parent[node] != node: parent[node] = find(parent[node]) return parent[node] n = int(input()) xlst, ylst, zlst = [],[],[] for i in range(n): ..

링크 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 코드 import bisect def LIS(arr): res = [arr[0]] for x in arr[1:]: if x < res[-1]: res[bisect.bisect_left(res,x)] = x continue res.append(x) return len(res) n = int(input()) line = sorted([list(map(int,input().split())) for _..

링크 : https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 코드 def DFS(idx,cnt,total): global answer if total == target: answer = min(answer,cnt) return if idx >= m: return DFS(idx+1, cnt+1, total | students[idx]) DFS(idx+1, cnt, total) n,m = map(int,input().split()) st..

링크 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 코드 def bf(start): dis = [0] * (n + 1) for i in range(n): for way in graph: cur,next_node,cost = way if dis[next_node] > dis[cur] + cost: dis[next_node] = dis[cur] + cost if i >= n-1: return False return True for..

링크 : https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**6) n = int(input()) inOrder, postOrder = list(map(int,input().split())), list(map(int,input().split())) arr = [0] * (n+1) for i in range(n): arr[inOrder[i]] = i def preOrder(inStart,inEnd,postS..

링크 : https://www.acmicpc.net/source/57235108 로그인 www.acmicpc.net 코드 ''' 먼저 처음 물을 대려면 우물을 먼저 하나 파야한다. 이 우물을 어디에 먼저 팔 것인가는 최소 스패닝 트리 문제 특성상 그리디하게 선정할 수 있을 것 같은데 어떤 기준으로 그리디하게 선정할 것인가가 문제이다. 1. 다른 논에서 끌어올 때 가장 많은 비용이 드는 것. 2. 우물을 팔 때 가장 적은 비용이 드는 것. 1번으로 했을 떄는 우물을 팔 떄 비용이 훨씬 더 엄청나게 많이 들 수도 있다는 단점이 존재한다. 2번으로 했을 때는 해당 우물은 적은 비용으로 팔 수 있을 지 몰라도 다른 논에 물을 댈 때 엄청나게 많은 비용이 발생할 수 있다. 그렇다면 2번으로 먼저 한 후에 어떤 논..

링크 : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 코드 from collections import defaultdict T = int(input()) n = int(input()) A = list(map(int, input().split())) m = int(input()) B = list(map(int, input().split())) sum_A, sum_..