[Happy Cow/G3/Python3]

13002번 Happy Cow G3

 

문제
천나라에 살고 있는 민호는 애지중지하는 소 한 마리가 있다. 소의 행복은 곧 민호의 행복이기 때문에 가지고 있는 전재산을 털어 최고로 맛있는 여물 N개를 구매 했다.민호는 여물을 관리하기 쉽게 폭은 좁지만 너비가 매우 긴 창고에 차례대로 넣었고, 왼쪽부터 한 개씩 1번, 2번, 3번,... , N번 여물이라 부르기로 했다. 각각의 여물들은 소가 먹었을 때 느끼는 행복이 다를수가 있다. 예를 들어 1번 여물을 먹으면 소가 느끼는 행복은 20이지만 2번 여물을 먹으면 소가 느끼는 행복은 10일 수가 있다는 것이다. 이를 편의상 행복도라 부르기로 하자. 그리고 여물들은 날이 지날수로 숙성이 되어 맛이 더 좋아져 행복도가 올라간다. 이는 (행복도 * 여물을 구매한 뒤 지난 날자)로 계산할 수 있다. 여물을 구매한 뒤 지난 날자는 구매한 당일의 날이 1이고 그다음 날이 2라고 계산한다. 이것들을 백만 년 숙성시킨 뒤 소에게 주면 소는 극락을 맛보겠지만 그때까지 기다릴 수 없던 민호는 여물을 구매한 날부터 N번째 날까지, 하루에 한 개의 여물을 소에게 주기로 하였다. 하지만 폭이 좁고 너비가 매우 긴 창고에 여물을 저장했기 때문에 중간에 있는 여물을 꺼내는건 불가능하고 왼쪽과 오른쪽, 양쪽 끝에서 하나만 꺼내 소에게 주는 것이 가능하다. 즉 i ≤ j (1 ≤ i ≤ j ≤ N)의 여물이 남아 있다면 민호는 i번 여물이나 j번 여물을 선택을 해서 소에게 줘야 한다는 뜻이다. i또는 j 외의 여물을 소에게 줄 수 없다. 민호는 소가 최대로 높은 행복을 느꼈으면 좋겠다고 생각한다. N일에 걸쳐 모든 여물을 소에게 줬을 때 소가 느끼는 행복도의 합이 최대가 되는 경우를 구해주자.

입력
첫 번째 줄에 여물의 개수 N (1 ≤ N ≤ 2000) 이 주어진다.
두 번째 줄에 여물의 행복도 Hi (1 ≤ Hi ≤ 1000, 1 ≤ i ≤ N) 이 공백을 구분으로 N개 주어진다.

출력
N일에 걸쳐 모든 여물을 소에게 줬을 때 소가 느낄 수 있는 행복도들의 합중 최대를 출력한다.

 

다이나믹 프로그래밍

 

dp 배열을 선언하고, 앞에서 먹은 개수, 뒤에서 먹은 개수를 인덱스로 사용해서 최댓값을 계산했다.

dp [left][right] = max(dp [left-1][right] + food [left] * 현재시간, dp [left][right-1] + food [-right] * 현재시간)로 점화식을 구할 수 있다.

인덱스 에러가 나지 않도록 조심해야한다.

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

t = 1
for i in range(1, n+1):
    for j in range(i+1):
        dp[i-j][j] = max((dp[i-j-1][j]+arr[i-j-1]*t) if i-j-1 >= 0 else 0, (dp[i-j][j-1] + arr[-j]*t) if j-1 >= 0 else 0)
    t+=1

result = dp[0][-1]
for i in range(n+1):
    result = max(result, dp[i][n-i])
    
print(result)

---

 

남은 음식이 동일할 때의 최댓값을 저장하는 것으로 아이디어를 얻었다.

인덱스 에러만 조심하면 좋을 듯 하다.