2157번: 여행첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1www.acmicpc.net 코드import sysinput = sys.stdin.readlinen, m, k = map(int, input().split())path = [[-1]*(n+1) for _ in range(n+1)] # path[i][j] : i->j로 갈 때 기내식 점수for _ in range(k): a, b, c = map(int, input().split()) if ..
DP
1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 코드 n, m = map(int, input().split()) d = [0]+[int(input()) for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] # i분에 지침 지수가 j일 때 최대 이동 거리 for i in range(1, n+1): dp[i][0] = max(dp[i-1][0], dp[i][0]) # 지침 지수 0에서 계속 쉬는 경우 for j in range(1, m+1): if j == 1 or dp[i-1..
2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 코드 n = int(input()) lst = [float(input()) for _ in range(n)] for i in range(1, n): lst[i] = max(lst[i], lst[i]*lst[i-1]) print("{:.3f}".format(max(lst))) 실수를 입력받았던 lst에 다이나믹 프로그래밍을 그대로 적용한다. lst가 i번째까지의 곱의 최댓값을 담는 배열이 된다. 이어지는 수열이 현재의 값보다 큰 경우, 즉 lst[i]..
10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 코드 for _ in range(int(input())): n = int(input()) x = list(map(int, input().split())) # 누적합 preSum = [0] for i in range(n): preSum.append(preSum[-1]+x[i]) # 브루트포스 ans = -int(1e9) for l in range(n): for r in range(l+1, n+1): if pre..
1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) n = int(input()) v = [0]+[int(input()) for _ in range(n)] dp = [[0]*(n+1) for _ in range(n+1)] def recursion(l, r, cnt): if l > r: return 0 if dp[l][r] != 0: return dp[l][r] dp[l][r] = max(v[l]*cnt+recursion(l+..
