99클럽 코테 스터디 20일차 TIL / 도둑질

도둑질

학습 키워드 : DP(다이나믹 프로그래밍)
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42897#

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한 조건

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

문제 풀이

효율성 테스트가 존재하고 집의 개수가 최대 100만개이기 때문에 DP로 풀어야만 하는 문제. 연속 두 번 선택을 못하는데 원형으로 이뤄진 배열일 경우 임의의 시작점을 포함하느냐 안하느냐의 경우의 수 두 가지로 나누었다. 코드의 dp1은 원형 고리의 시작점을 선택했을 때의 다이나믹 테이블이고 dp2는 시작점을 선택하지 않았을 경우이다.(대신 money 배열의 가장 끝에 있는 원소를 선택할 수 있다.)

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

    
    return max(dp1[-2],dp2[-1])

코멘트

dp1, dp2를 만들지 않고 dp로 먼저 dp1의 연산을 한 후 최댓값 저장한 뒤 dp를 초기화 하고 dp2 연산을 하는 것이 공간 낭비를 덜할 수 있을 것 같다. 하지만 for문을 두 번 돌기 때문에 시간은 조금 더 걸리고 코드가 덜 직관적일 수도 있겠다는 생각은 들었다. (워낙 짧은 코드라 크게 상관은 없는 문제들)