[백준] 수확

https://www.acmicpc.net/problem/1823

1823번: 수확

 

1. 문제 이해

1XN의 긴 밭의에 벼가 있고 양쪽 끝에서만 벼를 수확할 수 있습니다. 벼를 수확할 때 얻을 수 있는 이익은 K일에 수확할 경우 (벼의 가치 * K)를 얻을 수 있게 됩니다. 따라서, 양끝에서 벼를 어떤 순서로 수확하느냐에 따라 얻을 수 있는 이익이 달라지게 되는데 이중 얻을 수 있는 최대 이익을 계산해야합니다.

 

2. 문제 접근

첫번째 접근: 그리디

양쪽 끝에서만 벼를 수확할 수 있으므로 deque를 생각했습니다. 양끝에서 얻을 수 얻는 벼의 가치를 비교하여 더 가치가 낮은 벼를 수확하도록 했습니다. 왜냐하면 가치가 높은 벼일수록 더 나중에 수확해야 더 높은 이익을 얻을 수 있기 때문입니다. 하지만 이렇게 했을 때 반례가 존재했습니다. 2 2 1 2의 경우 1을 먼저 수확해야하는데 제 코드에서는 양끝이 같을 경우 왼쪽의 벼를 먼저 수확하도록 했기 때문에 틀렸습니다.

 

두번째 접근: 그리디

위의 반례를 해결하기 위해 양 끝의 벼의 가치가 같을 경우에는 투포인터를 활용해 안쪽으로 들어가면서 벼의 가치가 더 낮은 벼를 먼저 만나는 쪽을 수확하는 방식으로 변경하였습니다. 위의 예제에서는 오른쪽의 2가 1과 가까이에 있기 때문에 오른쪽 벼를 수확하도록 했습니다. 하지만 이 방식 역시 정해가 아니었습니다. 아직 반례는 찾지 못했습니다.

 

세번재 접근: DP

결국, 해결하지 못하고 구글링을 통해 힌트를 얻었습니다. 재귀 방식을 활용한 DP입니다. 

DP[left][right] = max(dp[left + 1][right] + nums[left] * depth + 1, dp[left][right - 1] + nums[right] * depth + 1)

가 점화식이 됩니다. 현재 범위가 left ~ right라고 가정했을 때 왼쪽에서 하나를 수확하거나 오른쪽에서 하나를 수확한 경우의 둘 중 더 큰 값을 택해주면 됩니다.

 

3. 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2000)

n = int(input())
nums = [int(input()) for i in range(n)]

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

def cal(left, right, depth):
    if left == right: return depth * nums[left]
    if dp[left][right]: return dp[left][right]
    dp[left][right] = max(cal(left + 1, right, depth + 1) + depth * nums[left], cal(left, right - 1, depth + 1) + depth * nums[right])
    return dp[left][right]

print(cal(0, n - 1, 1))

 

4. 회고

비슷한 문제가 를 풀어본 경험이 있어서 문제를 보자마자 deque와 그리디로 접근했는데 이것이 삽질의 이유였습니다. 이 문제는 K배만큼의 가중치가 붙기 때문에 그리디로는 풀이가 불가능한 것 같습니다. 지금까지 제 경험으로는 그리디로 보이는 문제는 DP로도 한번 접근해볼 필요가 있는 것 같습니다. 그리고 아직 이런 재귀와 DP를 같이 하는 방식에 익숙하지 않아서 쉽게 풀이를 떠올리지 못했습니다. 

 

5. 배운점

이 문제를 통해 배운 것이 또 하나있습니다. 바로 sys.setrecursionlimit()과 관련된 내용입니다. 재귀를 이용하는 풀이이기에 재귀의 횟수를 10 ** 8으로 늘렸는데 pypy3에서 메모리 초과가 발생했습니다. 그 이유는 setrecursionlimit()을 통해 재귀 횟수를 설정하면 그 만큼 스택의 메모리를 미리 잡아놓게 되는데 이게 메모리 초과를 유발한다고 합니다. pypy를 사용하는 경우 setrecursionlimit 사용에 유의해야합니다.