[프로그래머스 DP | python] 도둑질 🔥

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897?gad_source=1&gad_campaignid=22199869887&gbraid=0AAAAAC_c4nDRnLcdW5pfc_L8ay5k5GtDz&gclid=CjwKCAjwvO7CBhAqEiwA9q2YJbDF7ryyIw-S7pZMj8oNlBDm7aMbK_Yl8KqiJW-_lkRW9I8WZ5mdFRoCT4UQAvD_BwE
• 프로그래스 연습 

 

Q1) 문제를 어떻게 이해했나요?
A1) 원형으로 연결된 집들 중 인접한 두 집을 털 수 없을 때, 훔칠 수 있는 최대 금액을 구하는 동적 프로그래밍(DP) 문제

Q2) 문제를 어떻게 풀 예정인가요?
A2) 집들이 원형으로 연결되어 있기 때문에,
첫 번째 집을 털면 마지막 집은 못 털고, 마지막 집을 털면 첫 번째 집은 못 털어요.

따라서 두 가지 경우로 나누어서 계산해야 해요:
1. 첫 집을 포함하고 마지막 집을 제외한 경우
2. 첫 집을 제외하고 마지막 집을 포함한 경우
이 두 경우를 각각 계산한 후, 최댓값을 반환하면 됩니다!

Q3) 시간복잡도 구해보세요.
A3) 시간복잡도는 O(N)입니다.
원형 조건을 정확히 처리하는 분할 전략이 핵심입니다.

🔥 DP(Dynamic Programming)는 '동적 계획법'이라고 불리며,
복잡한 문제를 작은 부분 문제로 나누고,
이전 계산 결과를 저장해 중복 계산을 줄이는 최적화 기법입니다.

 

최적화된 코드

def solution(money):
    def rob(line): 
        n = len(line) # 집의 개수
        dp = [0] * n  # 각 집까지의 최댓값 저장 배열
        dp[0] = line[0] # 첫 번째 집만 털었을 때
        dp[1] = max(line[0], line[1]) # 첫 번째 또는 두 번째 중 더 큰 값을 선택
        
        for i in range(2, n):
        	# 현재 집을 털지 말지 선택 (전 집 그대로 vs 현재 집 + 전전집)
            dp[i] = max(dp[i-1], dp[i-2] + line[i])
        return dp[-1]
    
    return max(
        rob(money[:-1]),  # 첫 집 O, 마지막 집 X
        rob(money[1:])    # 첫 집 X, 마지막 집 O
    )

 

너무 헷갈린다...

🔍 핵심 설명

dp[i] = max(dp[i-1], dp[i-2] + line[i])

dp[i]는 i번째 집까지 고려했을 때의 최대 금액을 의미합니다.

1. dp[i-1]
   👉 i번째 집을 털지 않고, 이전 집까지의 최대 금액을 그대로 가져오는 경우입니다.
2. dp[i-2] + line[i]
   👉 i번째 집을 털고, 두 칸 전 집까지의 최대 금액에
   현재 집의 금액 line[i]를 더한 경우입니다.
   (왜 두 칸 전이냐면, 인접한 집은 털 수 없기 때문입니다!)

따라서 dp[i]는 이 두 가지 선택 중 더 큰 값, 즉 최적의 선택을 저장하게 됩니다.

여기서 중요한 건 dp[i-2]가 이미 최적의 경로를 저장하고 있다는 것이에요.
즉, i-2까지 가는 동안, "최대 금액을 얻기 위해 어떤 집을 털고 어떤 집을 안 털었는지"는 이미 dp[i-2] 안에 최선의 선택으로 계산되어 있어요.

 

• 예시1

money = [1, 2, 3, 1, 5]
# 인덱스:  0  1  2  3  4

# DP 배열 계산:
dp[0] = 1                     # 집 0만 털었을 때
dp[1] = max(1, 2) = 2         # 집 1만 털거나 0만 털거나 중 큰 값
dp[2] = max(2, 1+3) = 4       # 집 2 + 집 0, 또는 집 1만
dp[3] = max(4, 2+1) = 4       # 집 3 + 집 1 vs 이전 최대
dp[4] = max(4, 4+5) = 9       # 집 4 + 집 2 vs 이전 최대

 

• 예시2 [6, 7, 1, 30, 8, 2, 4]

🏠 Case 1: 첫 집 포함, 마지막 집 제외 ([6, 7, 1, 30, 8, 2])

i (집번호)	money[i]	dp[i] (현재까지 최대)	설명
0	6	6	첫 번째 집이므로 그대로 사용
1	7	max(6, 7) = 7	첫 번째와 두 번째 중 큰 값 선택
2	1	max(7, 6+1) = 7	2칸 전 + 현재와 바로 전 중 큰 값
3	30	max(7, 7+30) = 37	2칸 전 + 현재와 바로 전 중 큰 값
4	8	max(37, 7+8) = 37
5	2	max(37, 37+2) = 39

✅ 최종 결과: dp[5] = 39

 

🏠 Case 2: 첫 집 제외, 마지막 집 포함 ([7, 1, 30, 8, 2, 4])

i (집번호)	money[i]	dp[i] (현재까지 최대)	설명
0	7	7	첫 번째 집이므로 그대로 사용
1	1	max(7, 1) = 7	첫 번째와 두 번째 중 큰 값 선택
2	30	max(7, 7+30) = 37	2칸 전 + 현재와 바로 전 중 큰 값
3	8	max(37, 7+8) = 37
4	2	max(37, 37+2) = 39
5	4	max(39, 37+4) = 41

✅ 최종 결과: dp[5] = 41