[Python] 프로그래머스 땅따먹기 풀이

문제 확인

프로그래머스

나의 풀이

• 모든 경우의 수를 완전 탐색할 경우, 대략 $4^{100,000}$ 정도의 연산이 필요해 시간 초과가 발생한다.
• 따라서 다른 방법을 활용해야하고, 나는 DP를 활용했다.
• 매번 새로운 열만 밟을 수 있기 때문에, 현재 K 번째 열을 밟았다면, 이전엔 [K - 1, K - 2, K - 3]의 열만 밟을 수 있다.
• 결국 N 행의 K 번째 열을 밟았을 때의, 최대 값을 DP 테이블에 저장하면 문제를 풀 수 있다.
  • DP[n][k] = land[n][k] + max(DP[n - 1][k - 1] + DP[n - 1][k - 2] + DP[n - 1][k - 3])

# 땅 : (N, 4)
# 각 행의 1 칸만 밟을 수 있고 -> 연속 열 불가
# 완전 탐색 -> 4^(100,000) : 시간 초과
# DP[n][k] = a[n][k] + max(a[n-1][k -1] + a[n-1][k-2] + a[n-1][k-3])
def solution(land):
    dp = [[0 for _ in range(4)] for _ in range(len(land))]
    for i in range(len(land)):
        # 초기 성분 입력
        if i == 0:
            dp[0] = land[0]
            continue
        # DP 테이블 업데이트
        for j in range(4):
            dp[i][j] = land[i][j] + max([dp[i - 1][k] for k in range(4) if k != j])
    return max(dp[-1])

다른 사람 풀이

• j 번째 성분을 제외하기 위해서 land[i - 1][:j]와 land[i - 1][j + 1:]을 활용했다.

def solution(land):

    for i in range(1, len(land)):
        for j in range(len(land[0])):
            land[i][j] = max(land[i -1][: j] + land[i - 1][j + 1:]) + land[i][j]

    return max(land[-1])

프로그래머스