문제 바로가기
문제:
1 × N 크기의 긴 밭에 벼가 심어져 있다. 준희는 이 벼를 수확 하려고 한다. 그런데 가운데 있는 벼를 수확을 하려면 끝에서 가운데까지 헤집고 들어가야 하므로 양 끝에 있는 벼만 수확을 할 수 있다. 처음에는 첫 번째와 N번째 벼를 수확을 할 수 있을 것이며 만약에 첫 번째 벼를 수확을 하였다면 두 번째 벼와 N번째 벼를 수확을 할 수 있다. 수확을 하였을 때 얻을 수 있는 이익은 다음과 같다. 만약에 그 벼의 가치가 v(i)라고 하고 그 벼를 k번째로 수확을 한다고 하면 v(i) × k 만큼의 이익을 얻게 된다. 만약에 벼의 가치가 차례로 1 3 1 5 2 라고 하고 첫 번째, 다섯 번째, 두 번째, 세 번째, 네 번째의 순서대로 수확을 한다고 하면 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43 이 되어 43 만큼의 이익을 얻게 된다. 그리고 이 값이 저 벼로 얻을 수 있는 최대 이익이 된다. 우리가 구해야 할 값은 다음과 같다. 벼의 개수 N과 벼의 가치가 주어져 있을 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다.
출력:
첫째 줄에 얻을 수 있는 최대 이익을 출력한다.
풀이:
시도1.
import sys
from collections import deque
n = int(input())
lst = deque([int(input()) for _ in range(n)])
dp = [0] * (n + 1)
left, right = 0, -1 # 첫 인덱스, 마지막 인덱스
cal_num = 1 # 곱할 숫자
res = 0
while len(lst) >= 1: # n 보다 클 수 없음
res += cal_num * min(lst[left],lst[right])
if lst[left] > lst[right]:
lst.pop()
else:
lst.popleft()
cal_num += 1
print(res)
내 첫 시도의 아이디어는 투포인터를 사용하는거였다.
맨 왼쪽과 오른쪽을 비교해서, 작은 숫자와 곱해주면 된다고 생각을했다.
하지만 반례로
2 1 2 2 가 들어오면
양 쪽 숫자가 똑같게 된다. 그러면 안에까지 비교해야한다는것을 고려하지 않았다.
시도 2.
좀 생각을 한 후에 dp 를 써야 하는 문제인거는 알았지만, 어떻게 사용해야하는지는 몰랐다.. 결국 다른 사람의 힌트를 얻어 풀어냈다.
왼쪽 끝에서 올라오고, 오른쪽 끝에서 하나씩 올라온다고 생각해 이를 2차원 배열로 나타내면 된다.
예를들어 dp[1][3] 이면
왼쪽끝에서 첫 번째 까지 올라온 것이고, 오른쪽 끝에서 3번째 올라온 것이라고 생각하면 된다.
1 3 2 4 5로 예를 들어 본다.
dp[1][5] 은 11 이다.
dp[1][4] 일때 dp[1][5] 에 값은 변하지 않는다. >> dp가 성립될 조건이다.
dp[left][right] 는 left까지 수확 + right 까지 수확 했을때 최대
점화식으로 나타내면
dp[left][right] = max(
(dfs(left + 1, right, depth + 1) + lst[left] * depth),
(dfs(left, right - 1, depth + 1) + lst[right] * depth)
)
left 를 하나 더 수확하기 때문에 depth 와 lst[left] 를 곱해주면 된다.
left 와 right 로 가는 것 중에 어느것이 더 클지 모르므로 끝까지 재귀를 호출해 저장을 해 놔야한다.
import sys
sys.setrecursionlimit(2000)
n = int(input())
lst = [int(input()) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
def dfs(left, right, depth):
if left > right:
return 0
elif dp[left][right]:
return dp[left][right]
else:
dp[left][right] = max(
(dfs(left + 1, right, depth + 1) + lst[left] * depth),
(dfs(left, right - 1, depth + 1) + lst[right] * depth)
)
return dp[left][right]
print(dfs(0, n - 1, 1))
left 가 right 보다 커질일은 없으니 return 0을 해주고.
이미 계산되어있으면 그 값을 return 해준다.
elif 문이 없으면 시간초과가 나게 된다.
골3인데 굉장히 쉽다고 생각햇는데 역시나 아니였다.
dp문제 점화식 세우는것은 굉장히 어렵다.
댓글