문제 링크

바로가기

문제 풀이

풀이 1

import sys
sys.setrecursionlimit(10000)

answer = 0

def dfs(sum, cIndex, nRow, land):
    global answer
    
    if nRow == len(land):
        answer = max(answer, sum)
        return

    for i in range(4):
        if i == cIndex: continue
        dfs(sum + land[nRow][i], i, nRow + 1, land)

def solution(land):
    for i in range(4):
        dfs(land[0][i], i, 1, land)

    return answer

처음에는 dfs 재귀함수 방식으로 풀면 되지 않을까 생각했다. 테스트 케이스는 통과하였지만, 이렇게 풀면 범위가 100,000이기 때문에 시간 초과가 생길 수 밖에 없었다. 그래서 다른 방식으로 풀이를 바꾸었다.

풀이 2

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

두번째 풀이는 누적합 방식으로 풀었다. 땅을 돌면서 현재 인덱스 값을 이전 땅의 자기 자신과 같은 인덱스 값을 제외하고 나머지 세 값을 비교하고 누적하여 더해주는 방식으로 구현하였다. 이렇게 구현하면 O(N)으로 풀 수 있었다.

(빅오표기법에서는 상수를 제외하기 때문에 N)

새롭게 배운 점

1. 제한 사항을 보며 재귀나 bfs방식을 쓸 수 있는지 확인할 것.