https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net import sys import heapq INF = int(1e9) V, E = map(int, sys.stdin.readline().split()) k = int(sys.stdin.readline()) graph = [[] for _ in range(V + 1)] distance = [INF] * (V + E) for _ in range(E): u, v, w = ma..

입력 1. 노드 개수, 간선 개수 입력 2. 시작 노드 입력 3. 간선 개수의 라인만큼 a, b, c 입력 (a -> b, c의 비용) 출력 시작노드로부터 각 노드까지의 비용 출력 import heapq INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n + 1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) # 모든 간선 정보를 입력받기 for _ in ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n = int(input()) arr = list(map(int, input().split())) d = [0] * n d[0] = arr[0] for i in range(1, n): d[i] = max(arr[i - 1] + arr[i], arr[i], d[i - 1] + arr[i]) print(max(d)) 해설 간단한 DP 문제였다. d[i] = max(arr[i - 1] + arr[i], arr[i..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 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())) d = [0] * n for i in range(n): for j in range(i): if arr[i] > arr[j] and d[i] < d[j]: d[i] = d[j] d[i] += 1 print(max(d)) 해설..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net n = int(input()) data = [] for _ in range(n): data.append(list(map(int, input().split()))) for i in range(1, n): for j in range(3): if j == 0: data[i][j] = min(data[i - 1][1], data[i - 1][2]) + data[i][j] elif j..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net n = int(input()) data = [] for _ in range(n): data.append(list(map(int, input().split()))) k = 2 for i in range(1, n): for j in range(k): if j == 0: data[i][j] = data[i][j] + data[i - 1][j] elif i == j: data[i][j] = data[i][j] + data[i - 1][j - 1] else: data[i][j]..