프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12913

[나의 풀이]

⌛ 시간초과 (시간초과 케이스 다수 발생)

from collections import deque

def solution(land):
    answer = 0
    
    # 이전 x y 인덱스, 현재 점수
    queue = deque([(0,0,1),(0,1,2),(0,2,3),(0,3,5)])
    length = len(land)

    while queue:
        
        x,y,score = queue.popleft()
        
        if length>x+1:
        
            for idx,value in enumerate(land[x+1]):

                if y!=idx:
                    new = score+value
                    queue.append((x+1,y,new))
                    if new > answer:
                        answer = new

    return answer

입력된 Nx4 배열에서 행을 돌며 연속되지 않은 열의 값들을 더했을 때 최댓값을 구하는 문제입니다.🐨🐨🐨

문제를 이해하고 queue, BFS 구조로 구현해내는 데는 어렵지 않아 해결하는 듯했지만 대부분의 테스트 케이스에서 시간초과가 발생하였고 시간복잡도를 줄이는데 어려움이 있어 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(land):
    n = len(land)

    # dp[i][j] = i행 j열에서 점수의 최대값
    dp = [[0,0,0,0]] + land
    for i in range(1, n+1):
        dp[i][0] += max(dp[i-1][1], dp[i-1][2], dp[i-1][3])
        dp[i][1] += max(dp[i-1][0], dp[i-1][2], dp[i-1][3])
        dp[i][2] += max(dp[i-1][0], dp[i-1][1], dp[i-1][3])
        dp[i][3] += max(dp[i-1][0], dp[i-1][1], dp[i-1][2])

    return max(dp[n])

메모리를 할당하여 시간을 줄이는 DP를 활용하는 것이 포인트였습니다.🐇🐇🐇

각 행을 지날때마다 현재 위치의 열값을 제외한 값들 중의 가장 큰 값을 더한 뒤 저장하며 다음행으로 이동하는 방식입니다.

최대값을 구하는 문제이기 때문에 '나의 풀이'처럼 모든 경우의 수를 탐색하지 않고 max()로 현재 위치에서 가장 큰 값만 찾아 더하고 다음행으로 넘어가는 접근 방식으로 다가가면 되는 문제였습니다.

[다른 사람의 풀이2]

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])

유사하게 DP으로 해결한 풀이입니다. 각 행의 최대값을 더할때 슬라이싱을 활용하여 조금 더 간결한 표현으로 나타낸것을 볼 수 있었습니다.🐹🐹🐹

감사합니다.