목록도둑질 (1)

Scribbling

프로그래머스: 도둑질

연이은 값을 선택할 수 없는 문제는 전형적인 DP 문제로 많이 접해보았을 것이다. 다만 이 문제는 첫 번째 값과 마지막 값을 동시에 선택할 수 없다는 조건이 추가되어있다. 이에 따라, 첫 번째 값을 선택가능한 case와 마지막 값을 선택 가능한 case로 나누어 그 중 최댓값을 return한다. 1) 0th idx ~ (n-1)th idx 2) 1th idx ~ (n)th idx def solution(money): dp1 = [0] * (len(money) - 1) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) for i in range(2, len(money)-1): dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) dp2 = [0..
Computer Science/Coding Test 2021. 10. 26. 22:17
이전 Prev 1 Next 다음