한참 예전에 이와 비슷한 cycle 이 있는 배열 dp 문제를 풀었는데 그보다 시간이 지난 뒤에 못 풀어서 당황했던 기억이 있다. 그 당시엔 아마 배열 마지막 집 전까지 dp 업데이트 후 첫번째 집과 마지막 집 value 를 비교했던것 같은데, 위험한 접근이고 edge case 도 매우 많았을 거라 생각된다.
접근법대로 생각이 든다면 일단 dp가 만들어지고 난 후 첫번째(또는 마지막) 집을 털었는지 여부는 내가 신경쓰지 않아도 된다.
이유는 크게 두 가지 경우의 수로 나누어 생각해보면 알 수 있다.
만약 0, len(배열) - 1 의 배열에서 나온 값이 첫번째 집을 털고 나온 최적값이라면 이는 저절로 1, len(배열) 의 배열에서 나온 값 -이 dp 에서 마지막을 털었건 안 털었건 상관 없다- 과 마지막 단계에서 비교된다.
아니면 첫번째 배열에서 나온 값이 첫번째 집을 털지 않고 나온 최적값이라면 이는 두번째 집을 포함한 이후 집들 중에서 처음으로 턴 집이 나오게 된다. 결국 이 첫번째 배열의 최적값은 두번째 배열의 최적값과 1. 같거나 (최적값이 마지막에서 두번째 집을 털었을 경우), 2. 마지막 집 값만큼 더 작다(마지막에서 두번째 집을 털지 않았을 경우).
직관적으로 풀린다면 좋은 신호지만 아직 답을 써도 내일 보면 이게 왜 정확하지? 란 생각이 드는 dp 어린이기에 의심이 풀릴때까지 따져보는 것은 필요한 과정이다.
class Solution:
def rob(self, nums: list[int]) -> int:
if len(nums) == 1:
return nums[0]
# if we rub, record it on first column 0
# first exclude the last house
dp = [[0] * 2 for _ in range(len(nums) - 1)]
dp[0][0] = nums[0]
for i in range(1, len(nums) - 1):
dp[i][0] = dp[i - 1][1] + nums[i]
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1])
temp = max(dp[len(nums) - 2])
# then exclude the first house
dp[0][0] = nums[1]
for i in range(1, len(nums) - 1):
dp[i][0] = dp[i - 1][1] + nums[i + 1]
dp[i][1] = max(dp[i - 1][0], dp[i - 1][1])
return max(temp, max(dp[len(nums) - 2]))