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

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

푼 사람들이 왤케 적은지 알겠다.

 

쉬운 거 같은데 막상 해보면 어려움

 

 

처음에 index도 따로 받아서 들어온 행마다 max값을 구해주고 그 인덱스에 해당하는 다음 행들의 열 값을 0으로 바꾼 다음 max 값을 구해주는 방식으로 하려 했는데

 

만약 다음 행의 max 값이 이전 행의 max값보다 클 때 구멍이 생겨 최댓값을 구할 수 없게 된다.

 

 

구글링해봤더니 첫 행의 max값을 다음 행에 더해주는 것으로 하는 방식이 최적인 것 같았다. (같은 열인 경우 제외)

 

 

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

참고: https://codingspooning.tistory.com/106

 

 

 

실행하면 이렇게 된다.

두번째 행에서 10, 11, 12, 11 이 되는 이유는 5 와 8 이 같은 열이기 때문

 

다 더한 뒤 마지막 행의 max 값만 구해주면 된다.