[DP] 땅따먹기 - Python

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

프로그래머스

 

[문제 간단 요약]

1. 주어진 배열을 한 행씩 선택, 연속으로 같은 열 선택 불가

2. 최종적으로 누적된 숫자의 합이 최대가 되도록 하는 문제

 

[문제 해결 방안]

✅ DP(동적 계획법) 문제

• 각 칸에서 이전 행의 같은 열을 제외한 나머지 열 중 최댓값을 선택해 더하는 방식

[문제 해결 코드] - 초기 코드

• 시간 복잡도: O(N)
• 공간 복잡도: O(N) (DP 배열 별도 사용)

def solution(land):
    answer = 0
    dp_map = [[0]*4 for _ in land]
    for i in range(4):
        dp_map[0][i] = land[0][i]
    for depth in range(1, len(land)):
        for k in range(4):
            for idx in range(4):
                if k == idx: continue
                dp_map[depth][k] = max(dp_map[depth][k],dp_map[depth-1][idx] + land[depth][k])
    return max(dp_map[-1])

 

[문제 해결 코드] - 개선 코드

• 시간 복잡도: O(N)
• 공간 복잡도: O(1) (기존 배열 활용)

def solution(land):
    for i in range(1, len(land)):
        for j in range(4):
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
    return max(land[-1])

 

[코드 개선점]

초기 코드의 문제점

• 별도의 DP 배열(dp_map)을 사용해 메모리 공간이 추가 필요
• 중첩 반복문이 코드가 복잡하고 이해하기 어려움

개선된 코드의 장점

• 원본 배열을 직접 수정하여 메모리 효율성이 개선
• 중첩 반복문을 2중으로 간소화하여 가독성 증가