[코딩테스트] 프로그래머스 땅따먹기 파이썬(Python)

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

프로그래머스

이 문제는 다이나믹 프로그래밍과 그리디알고리즘을 이용하여 문제를 해결했습니다.

풀이를 위한 기본적인 아이디어는 이전 행 중 현재 자기 자신의 인덱스를 제외한 최댓값을 현재값에 더하기 입니다.

저의 풀이방법은 아래와 같고, 저의 풀이방법을 개선한 풀이방법들을 가지고 왔습니다.

첫번째 풀이

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

land의 모든 행을 순회하는데 0부터 시작하면 0번째 인덱스의 이전 행을 찾을 수 없기 때문에 1부터 시작합니다.
현재 행에 있는 모든 원소를 또한 순회합니다.

이때 이전 행 또한 순회하면서 현재 행의 인덱스와 이전 행의 인덱스가 다른 값만 비교하여 최댓값을 찾아냅니다
찾아낸 최대값을 현재 값에 더합니다.

 

모든 반복문이 종료되면 max(land[-1])로 가장 마지막 행의 최대값을 반환합니다.

 

위의 풀이를 개선한 두번째 풀이입니다.

두번째 풀이

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

land를 순회하는 것을 첫번째 풀이와 동일하지만
최댓값을 찾아내는 과정은 다릅니다.

첫번째 풀이에서는 이전 행의 모든 원소를 반복하여 최댓값을 찾아냈지만
두번째 풀이에서는 반복문을 사용하지 않고 현재 행의 인덱스를 제외한 이전 행의 값들을 리스트로 만들어 max()함수를 이용하여 찾아내고 있습니다.

 

두번째 풀이 방법이 첫번째 풀이 방법보다 속도가 조금 더 빠르고 가독성도 좋아보입니다

세번째 풀이

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

세번째 풀이 방법은 두 번째 풀이 방법에서 반복문을 제거하여 해결한 방법입니다.

 

두 번째 풀이에서는 현재 행의 인덱스를 제외한 리스트를 찾아내 더하고 max를 하는 과정이 존재하지만

세번쨰 풀이에서는 그 과정 대신 바로 원소에 접근하기 때문에 두번째 풀이방법보다 계산 속도가 빠른것 같습니다.