[코딩테스트] 프로그래머스 - 땅따먹기 (Lv.2) in Python

땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하세요.

 

예시:

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

 

=> 5 -> 7 -> 4 => answer = 16

 

programmers.co.kr/learn/courses/30/lessons/12913

 

풀이

- 처음에는, 1행에서 가장 큰 숫자를 찾고, 다음 행에서 같은 열에 있는 숫자를 제외한 max 숫자를 찾고, 이런 식으로 풀었다.

 

- 하지만 1행에서의 max가 전체 max에 큰 영향을 주지 않을 때, 이 풀이는 올바르지 않다.

ex. | 1 | 2 | 3 | 5 |
    | 5 | 6 | 7 | 100 |
    | 4 | 3 | 2 | 1 |

=> 이 경우, 5 -> 7 -> 4보다, 3 -> 100 -> 4 가 더 큰 answer를 반환한다.

 

- 따라서, 각각의 행에서, 최적의 결과를 내는 답을 trace해야한다.

=> 동적계획법을 사용!!

 

동적계획법

주어진 최적화 문제를 // 재귀적인 방식으로 보다 작은 부분으로 나누어 // 점화식과 재귀적 구조로 부분 문제를 풀어, // 이 해를 조합하여  전체 문제의 해답을 구하는 방식이다.

 

동적계획법을 사용했고, 이 문제와 비슷한 문제인 격자상의 경로문제 풀이를 잘 정리해주신 이 블로그 글이 많이 도움이 되었다.

- wooder2050.medium.com/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0

동적계획법(Dynamic Programming) 정리

 

 

Back to 풀이..

- 문제의 답을 점화식 (Recurrence Relation)으로 풀어보자면,

sum(x, y) = max( sum(x - 1)행의, y열의 원소를 제외한 모든 원소)) + value(x, y) 

라고 볼 수 있다.

 

- 따라서, 현재 자리 (x, y)에 오기까지의, 가장 합이 큰 경로를 따라온 최적의 답을 저장하는 배열 sumArr를 만들고,

한 행, 한 열씩 채워준 후,

- 마지막 행의 최대값을 구해주면, 그것이 답이다.

 

파이썬 구현

def solution(land):
    numRow = len(land)
    numCol = len(land[0])

    sumArr = [land[0]]
    
    for i in range(1, numRow):
        sumArr.append([0]*numCol)
        for j in range(numCol):
            target =  [x for x in sumArr[i-1]]
            target.pop(j)
            sumArr[i][j] = max(target) + land[i][j]
                
    answer = max (sumArr[numRow - 1])
    
    return answer

이 경우, land가 아까와 같이

land = [[1,2,3,5],
	[5,6,7,8],
        [4,3,2,1]]

라면,

sumArr = [[1, 2, 3, 5],
	[10, 11, 12, 11],
        [16, 15, 13, 13]]

이 되어, 올바른 답인 16을 return한다.

 

 

다른 분들의 풀이

- 굳이 새로운 배열을 만들지 않고,

  주어진 land자체를 바꾸며,

  list slicing으로 코드를 훨씬 더 간소화시킨

  다음의 풀이를 복기한다.

 

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

 

- list slicing은, index가 range를 벗어나도, IndexError을 일으키지 않는다!!!

일으킬 것이라 지레짐작하고 사용하지 않았는데, 좋은 것을 배웠다.

 

arr = [1, 2, 3]

print(arr[3:]) # []

print(arr[3])# IndexError

 

이에 대한 Stack Overflow 질문&답변

- stackoverflow.com/questions/9490058/why-does-substring-slicing-with-index-out-of-range-work

Why does substring slicing with index out of range work?