[프로그래머스] 땅따먹기 (python)

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

프로그래머스

 

 

땅따먹기 게임에서는 한 행씩 내려오면서 진행된다.

 

그렇다면 반복문으로 한 행씩 내려가면서 주어진 land에 값을 저장하는 식으로 구현하면 된다.

 

그리고 같은 행을 밟을 수 없다고 했으니, 같은 행을 밟지 않으면서 최댓값을 가질 수 있도록 해야 한다.

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

    return max(land[len(land) - 1])

코드에서 바깥쪽 반복문을 보면, 1부터 len(land)까지 순회한다고 나와있다.

 

첫 번째 줄은 더하는 대상이 아니므로 그대로 넘어간다. 그래서 두 번째 줄부터 시작한다.

 

안쪽 반복문에서는 각 줄을 순회하면서 바로 위 행부터 현재 열을 제외한 나머지 값들 중 최대값을 현재 값에 더한다.

land[i][j] += max(land[i - 1][:j] + land[i - 1][j + 1:])

 

이 부분을 조금 자세히 살펴보겠다.

• land\[i - 1\]\[:j\]: 이전 행의 첫 번째부터 j - 1번째 요소들로 구성된 리스트
• land\[i - 1\]\[j + 1:\]: 이전 행의 j + 1번째부터 마지막 요소들로 구성된 리스트
• 가운데 덧셈 기호는 값을 더하는게 아니라, 리스트를 결합하기 위해 쓰인 것이다.

 

references

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

프로그래머스