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..
dynamicprogramming
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+..
4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 코드 import sys input = sys.stdin.readline while True: n, m = map(int, input().split()) if n == 0 and m == 0: break matrix = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] ans = 0 for i in range(1, n+1): for ..
17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 코드 n, m = map(int, input().split()) fuels = [list(map(int, input().split())) for _ in range(n)] dp = [[[int(1e9)]*3 for _ in range(m)] for _ in range(n+1)] for j in range(m): for k in range(3): dp[0][j][k] = 0 for i in range(1, n+1): for j in ..
13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 문제 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매하고 있다. 게다가 연속 3일권, 연속 5일권에는 쿠폰이 각각 1장, 2장이 함께..
