
링크 : https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 코드 import sys input = sys.stdin.readline for _ in range(int(input())): n = int(input()) rank = list(map(int,input().split())) degree = [0] * (n + 1) for i,v in enumerate(rank): degree[v] = i graph = [*degree] m = i..

링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 코드 a = "0"+input() b = "0"+input() dp = [[0] * (len(b)) for _ in range(len(a))] for i in range(1,len(a)): for j in range(1,len(b)): dp[i][j] = dp[i-1][j-1] + 1 if a[i] == b[j] else max(dp[i-..

링크 : https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 코드 import heapq as hq import sys input = sys.stdin.readline n = int(input()) station = [] for _ in range(n): hq.heappush(station,list(map(int,input().split()))) l,p = map(int,input().split()) cn..

링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline INF = 2147000000 n = int(input()) rgb = [] ans = INF for _ in range(n): rgb.append(list(map(int, input().split()))) for i in range(3): dp = [[INF, INF, INF] f..

링크 : https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline def merge(x,y): return x * y def init(node,left,right): if left == right: stree[node] = arr[left] return stree[node] mid = (left+right)//2 ..

링크 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 코드 n = int(input()) arr = list(map(int,input().split())) dp = [1] * n for i in range(n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i],dp[j]+1) a = max(dp) pr..

링크 : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 코드 import heapq import sys input = sys.stdin.readline n,m = map(int,input().split()) first = [[] for _ in range(n+1)] link = [0 for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split())..

링크 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 코드 import sys input = sys.stdin.readline def union(a,b): a, b = find(a), find(b) if a == b: return network[a] parents[b] = a network[a] += network[b] return network[a] def find(node): if parents[node] != node:..

링크 : https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 코드 def BFS(s): visited = [[False] * (total + 1) for _ in range(total+1)] a,b = s[0],s[1] Q = deque() Q.append((a,b)) visited[a][b] = True while Q: x,y = Q.popleft() z = total - x - y if x == y == z: return True for ..