문제
나의 풀이
해당 문제는 풀지 못했다.
그런데 풀이 방법을 듣고 보니, 왜 이런 생각을 하지 못했을까 하는 생각이 든다.(무언가 간단해 보였기 때문에)
다른 사람의 풀이
스터디 원에게 힌트를 달라고 해서 들었는데, 그 힌트를 들으니 너무 쉬워져 버렸다.
이 문제는 dp로 풀어야 한다고 하지만, dp를 꺼낼 것도 없이 간단한 문제라고 생각된다.(물론 못풀긴 했지만 하하..)
단계를 나눠서 생각해보면 어땠을까 싶다.
[1,2,3,5]
[5,6,7,8]
[1,1,1,100]
이렇게 세 개의 배열이 있을 때,
3->5는 두 번째 배열까지의 최댓값이지만
세 번째 배열에서는 5->7->100 이 최대값이다.따라서 다음 배열로 넘어갈 때, 가장 알맞는 선택을 하려면 선택한 배열 이전의 최선의 합계들을 알고 있어야 가능하다.
이것에 대한 구현을
이런 식으로 할 수 있었다.def solution(lands): start = [0,0,0,0] for land in lands: start = [land[0]+max(start[1:]), land[1]+max(start[0:1]+start[2:]), land[2]+max(start[:2]+start[3:4]), land[3]+max(start[:3])] return max(start)
