[프로그래머스] Lv2. 땅따먹기

📝 문제

풀이

❌ 백트래킹

N이 10만이었지만 그래도 도전해봤다
장렬하게 실패했다

2차원 배열에서 가장 큰 값을 찾아서 백트래킹도 시도했지만 소용 없었다

def solution(land):
    answer = 0
    L = len(land)
    
    max_x = max([max(row) for row in land])
    def eat_ground(row, col, score):
        nonlocal answer
        # 마지막 행까지 더해도 최대값이 될 수 없는 경우
        if (L - row) * max_x + score <= answer:
            return 
        
        # 마지막 행까지 도달했을 때
        if row == L:
            answer = max(answer, score)
            return 
        
        for j, x in enumerate(land[row]):
            if j != col:
                eat_ground(row+1, j, score+x)
        
    eat_ground(0, -1, 0)
    return answer


import sys
sys.setrecursionlimit(100001)

⭕️ 동적 계획법

land[i][j]에서 가질 수 있는 최대값 = land[i-1]행에서 j열을 제외한 열들의 값 중 최대값이다

def solution(land):
    N = len(land)
    dp = [[0, 0, 0, 0] for _ in range(N)]
    dp[0] = land[0]
    
    for i in range(1, N):
        dp[i][0] = land[i][0] + max(dp[i-1][1], dp[i-1][2], dp[i-1][3])
        dp[i][1] = land[i][1] + max(dp[i-1][0], dp[i-1][2], dp[i-1][3])
        dp[i][2] = land[i][2] + max(dp[i-1][0], dp[i-1][1], dp[i-1][3])
        dp[i][3] = land[i][3] + max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
        
    return max(dp[N-1])

후기

dp로 풀어야 되는지 몰랐다
10만이니까...안되는구나...