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

 

문제 풀이

어... 처음에는 dp처럼 이전 계산 결과를 다 저장한다음에 마지막에 경로값을 쓰는? 문제인줄 알았으나 읽다보다 더 쉬운문제였다. 마지막에 계산 결과중 제일 큰값을 출력하면 되는 문제다.

 

그렇다면 이전 결과중에 제일 큰값 들만 저장하면서 진행하고, 마지막 결과값중에 제일 큰값을 찾아내면 된다는 얘기다.

row의 각 값은 이전 값들과의 계산중 가장 큰값만을 저장하면 된다.

 

[1, 2, 3, 5]

[5, 6, 7, 8] → 이 단계에서 계산을 보면 (자신의 index와 같은 index는 피해서)

5 → [5+2, 5+3, 5+5] → max=10

6 → [6+1, 6+3, 6+5] → max=11

7 → [7+1, 7+2, 7+5] → max=12

8 → [8+1, 8+2, 8+3] → max=11

[9,10,12,11] 이라는 row를 얻는다.

 

[9, 10, 12, 11]

[4, 3, 2, 1] → 이 단계에서 계산을 보면

4 → [4+10, 4+12,4+11] → max =16

...

이런식으로 차례차례 내려가면서 max값들로만 row를 채우면 금방 값을 구할수 있다.

(for loop * 2 인데도 효율성이 통과됐다!)

 

코드

def solution(land):
    answer = 0
    
    sum_list = land[0]
    for row in land[1:]:
        temp_list = []
        for index, num in enumerate(row):
            max_num = max(sum_list[:index]+sum_list[index+1:])
            temp_list.append(num+max_num)
        sum_list = temp_list
        
    answer = max(sum_list)
    return answer

 

문제는 여기

https://programmers.co.kr/learn/courses/30/lessons/12913?language=python3 

코딩테스트 연습 - 땅따먹기