접근
시도 1
먼저 머리속으로 생각해보니까 n 번째 창고를 공격할지에 대한 여부는 n + 1 번째의 창고의 식량과 n - 1 번째의 식량의 크기에 따라 달라진다는 것을 깨달았다. 따라서 피보나치와 비슷하게 재귀로 하면 되겠다고 생각하여 풀어보았다.
tmp = [0] + storages.copy()
ans = [0] * 1001
ans[1] = tmp[1]
def recur(x):
if ans[x] != 0:
return ans[x]
if recur(x + 1) + recur(x - 1) > tmp[x]:
tmp[x] = 0
ans[x] = tmp[x]
return tmp[x]
recur(n)
print(sum(tmp))하지만 이렇게 간단하지 않았다. 생각해보니까 n - 1 번째 창고를 털 수 있을지에 대한 여부도 n - 2 번째와 n 번째의 크기에 따라 달랐고 창고를 털었는지 여부에 따라서 달랐다. 또한 재귀를 너무 많이 했다는 오류도 발생하여 재귀보다는 반복문으로 접근해야겠다고 생각했다.
시도2
앞서 배웠던 메모이제이션을 활용하여 이전 결과를 메모리에 저장하여 필요없는 계산을 줄이는 방식으로 접근해보았다.
d = [[0]] * 101
d[1] = [storages[0]]
d[2] = [0, storages[1]]
d[3] = [storages[0],storages[2]]
# x 가 0 이 아니였을 떄 앞에 값들에 합
def memo(x):
if sum(d[x]) != 0:
return d[x]
tmp_1 = memo(x - 1) + [0]
tmp_2 = memo(x - 2) + [storages[x - 1]]
if sum(tmp_1) > sum(tmp_2):
d[x] = tmp_1
else:
d[x] = tmp_2
return d[x]
memo(n)
print(sum(d[n]))이렇게 하면 예제의 테스트케이스는 답이 잘 나오나 모든 경우는 못잡았다. 예를 들어서 [1, 3, 1, 5, 7, 7, 8] 이런식으로 식량 창고가 있으면 위의 방법을 했을 때는 17 이 나오지만 생각해보면 답은 [3, 7, 8] 이렇게 3개만 공격하는 것이 최대값이 나온다. 따라서 이 방법도 모든 경우를 계산하기엔 부족하다.
생각해보면 n 번째 창고를 공격할지 여부는 n - 3 번째 까지의 결과와는 무관하다는 것 또한 깨달았다.
하지만 여기까지 하고 답을 보는게 좋겠다고 생각하여 해설을 보았다.
해설
d = [0] * 100
d[0] = storages[0]
d[1] = max(storages[0], storages[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + storages[i])
print(d[n - 1])해설은 허탈할정도로 너무 간단했다. 그냥 n 개의 창고가 있을 때 최대로 얻을 수 있는 값을 메모리에 저장했으면 됐다. 내가 놓친점은 다음과 같았다.
- n 번째 창고를 공격했을지에 대한 여부와 d[n] 과는 상관이 없다.
- 단순히 d[n - 2] + n 번째 창고식량과 d[n - 1] 을 비교하면 된다.
나는 n 번째 창고를 공격할수 있을지에 대한 여부는 n - 1 번째 창고를 공격했는지에 여부에 따라 다르고 n - 1 번째 창고를 공격할지에 대한 여부 또한 n - 2 번째와 연관 있으므로 n 번째 창고의 공격 여부는 n - 2번째와도 연관이 있다고 생각했다.
하지만 이는 중요하지 않았다. n - 2 번째의 창고를 공격했는지 안했는지는 n 번째 창고를 공격할지에 대한 여부와 상관 없다. 단순히 d[n - 2] 는 n - 2개의 창고가 있을 때 얻을 수 있는 최대 값이 들어와 있고 n - 2 번째 창고의 공격 여부는 n 번째 창고를 공격할지에 대해 영향을 끼치지 않는다. 왜냐하면 서로 붙어있지 않기 때문이다.
n - 2 번째 창고를 공격했던 안했던 d[n - 2]에는 최대값이 들어있고 n 번째 창고를 당연히 공격할 수 있으므로 d[n - 2] + n 번째 창고식량 과 d[n - 1] 의 값중 큰 값을 d[n] 에 넣으면 된다.
