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

🔑 오늘의 학습 키워드 DP

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/42897

 

def solution(money):
    answer = 0

    dp1 = [0] * len(money) # 첫 집을 털었을 때
    dp2 = [0] * len(money) # 첫 집을 안 털고 두 번째 집을 털었을 때

    dp1[0] = money[0]
    dp1[1] = dp1[0]
    dp2[1] = money[1]

    for i in range(2, len(money) - 1):
        dp1[i] = max(dp1[i - 1], dp1[i - 2] + money[i])
        dp2[i] = max(dp2[i - 1], dp2[i - 2] + money[i])

    dp1[-1] = dp1[-2]
    dp2[-1] = max(dp2[-2], dp2[-3] + money[-1])
    answer = max(dp1[-1], dp2[-1])

    return answer

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

dp네 근데 원형? 어떻게 처리하지

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

😎 알고리즘 개요

DP 유형을 많이 풀면 이정도는 쉬운데

 

이 문제에는 첫번째 집을 골랐을 때 마지막 집이랑 연결이 되어 있어서 그 부분을 고려해줘야 한다.

 

그래서 첫번째 집을 고르는 경우와 안 고르는 경우로 나누어서 DP를 적용했다.

✅ 오늘의 회고

- DP

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL