Programmers. 도둑질

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 도둑질

문제 풀이

직선에서의 똑같은 문제는 막힘없이 풀었는데 원형이 되자마자 막혀버렸다. 첫 집을 방문하면 이전 집(마지막 집)은 방문하면 안된다는 사실을 알아야 한다. 즉, 마지막 값을 방문하려면 첫 집을 방문하지 않아야 함을 의미하므로 dp 배열을 두 개 생성해야 한다.

• 주어진 집의 개수만큼의 dp 배열 생성
• 첫 집은 무조건 방문하는 경우 0, 1번 index 값 설정, 첫 집을 방문하지 않는 경우 0, 1번 index 설정
• 이후 2부터 N - 1까지 i번째 항은 i - 2까지의 최대값과 i번째 집을 더한 값, i - 1까지의 최대값을 비교하여 더 큰값으로 설정한다.
• dp 배열의 최대값들을 비교해 다른 값 리턴

python 코드

def solution(money):
    N = len(money)
    dp1 = [0] * N
    dp2 = [0] * N
    dp1[0], dp1[1] = money[0], max(money[0], money[1])
    dp2[0], dp2[1] = 0, money[1]
    for i in range(2, N):
        if i == N - 1:
            dp1[i] = max(dp1[i - 2], dp1[i - 1])
            dp2[i] = max(dp2[i - 2] + money[i], dp2[i - 2])
            continue
        dp1[i] = max(dp1[i - 2] + money[i], dp1[i - 1])
        dp2[i] = max(dp2[i - 2] + money[i], dp2[i - 1])
    return max(max(dp1), max(dp2))