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]..
문제풀이/DP
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장이 함께..
