99클럽 코테 스터디 12일차 TIL 프로그래머스 도둑질

프로그래머스 도둑질

오늘의 문제도 DP문제다.

이 문제는 원형 DP 문제로 백준에도 RGB거리 2라는 비슷한 DP 문제를 풀어 봤었다.

https://www.acmicpc.net/problem/17404

보자마자 어떻게 풀지 방향성이 정해져서 몇번 시도 후 바로 정답을 구할 수 있었다.

핵심 아이디어는 기본적인 DP처럼 1을 골랐을때, 안골랐을때 => 2를 골랐을 때는 1을 안고른 누적합을 참고하고, 2를 안골랐을때는 1을 고른 누적합을 참고하면, 결과적으로 연속되지 않은 경우들을 골랐을때의 최대 합을 구할 수 있다.

1을 고르면 => 마지막것은 못고르는 것 중 최대

2를 고르면 => 마지막것을 고르거나 못고른 것 중 최대

나의 코드

def solution(money):
    # 1. dp1 0번째를 골랐을때
    # 2. dp2 1번째를 골랐을때
    dp1=[[0,0] for _ in range(len(money))]
    dp1[0][0]=money[0]
    for i in range(len(money)-1):
        dp1[i+1][0]=dp1[i][1]+money[i+1]
        dp1[i+1][1]=max(dp1[i])
    
    dp2=[[0,0] for _ in range(len(money))]
    dp2[1][0]=money[1]
    for i in range(len(money)-1):
        dp2[i+1][0]=dp2[i][1]+money[i+1]
        dp2[i+1][1]=max(dp2[i])
    return max(max(dp1[-2]),max(dp2[-1]))

오늘의 회고

오늘은 원형 DP를 오랜만에 풀어 보았는데, 이전에 고통받으며 고민하고, 풀어본 경험을 바탕으로 DP문제를 수월하게 풀게되어 아주 기뻣다.

내일은 얼마 남지 않은 면접을 준비하고, 다시 자바공부를 진행 할 것이다.