[Python 파이썬] 프로그래머스 - 땅따먹기

2024년 9월 10일

문제 링크 : 프로그래머스 - 땅따먹기

---

문제 접근

 

0번째 행부터 마지막 행까지 규칙에 맞춰 칸을 한 칸 씩 밟아가며, 최대로 많이 누적시킬 수 있는 점수를 출력하는 문제이다.

 

여기서 말한 규칙은 다음과 같다.

 

땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

만약 1번째 열의 칸을 밟았다면, 다음 행에선 1번째 열 칸은 밟지 못한다는 의미이다.

 

마지막 행까지 도달하는 모든 경우의 수를 계산하기엔 최대 행의 개수가 100,000개로 시간복잡도가 엄청 불어나게 된다.

 

이를 효율적으로 풀기 위해 다이나믹 프로그래밍 기법을 활용하기로 결정하였다.

 

DP(다이나믹 프로그래밍) 기법을 활용하고자 결정한 이유는 다음과 같다.

 

특정 칸 까지 누적할 수 있는 최대 값만 모두 저장한다면, 불필요한 연산을 생략할 수 있다.

 

문제의 예시를 그대로 가져와 DP를 어떻게 활용하는지 확인해보자.

 

초기 상태

 

land는 입력값이며, land와 같은 사이즈의 DP Table을 선언한다. DP Table 각 칸의 요소는 현재 칸 까지 도달하여 누적된 점수 중 최대값을 저장한다 라고 이해하면 된다.

 

 

land의 0번째 행은 각 칸까지 도달하는 경우의 수가 자기자신 칸을 밟은 경우밖에 존재하지 않으므로, 각 칸의 값을 그대로 DP Table에 옮겨준다.

 

 

1번째 행의 각 열 까지의 누적 점수의 최대값을 위와 같이 기입해준다.

 

1행 0열의 값은, 0행의 0열을 제외한 각 열 까지의 최대 누적 점수 값 + 1행 0열의 점수 중 최대 값을 채택하면 된다.

 

 

위와 같은 방법으로 윗 행의 각 열들 중, 현재 밟으려는 땅이 속한 열과 다른 열 까지의 최대 누적 점수를 현재 밟으려는 땅의 점수와 더해 해당 값을 최대값으로 채택하는 방식을 반복하면 된다.

 

 

 

 

 

 

 

 

 

 

DP Table의 모든 요소를 채웠으니, 로직을 종료한다.

 

 

문제에서 원하는 바는, 마지막 행까지 도달하는 경우의 수들 중, 최대 누적 점수를 구하는 것이기 때문에, DP Table의 마지막 행의 최대값을 출력해주면 된다.

---

전체 코드

 

def solution(land):

    length = len(land)

    now_row = 1
    dp = [[0 for _ in range(4)] for _ in range(length)]
    dp[0] = land[0][:]

    while now_row < len(land):
        for now_col in range(4):

            max_value = 0

            for last_col in range(4):

                if now_col == last_col:
                    continue

                max_value = max(max_value, dp[now_row - 1][last_col] + land[now_row][now_col])
            
            dp[now_row][now_col] = max_value

        now_row += 1
    
    return max(dp[-1])

if __name__ == "__main__":
    land = [[1,2,3,5],[5,6,7,8],[4,3,2,1]]
    print(solution(land))

---

풀이 후기

 

dp를 활용할 수 있는 문제였다.