[Programmers][Python][동적계획법, DP] 정수 삼각형- level3

 

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

코딩테스트 연습 - 정수 삼각형

 

동적 계획법 카테고리에 있는 level 3 문제입니다.

문제풀이에 집중하다보니 결과물은 가독성이 떨어지는 코드네요 ㅠ 죄송합니다. 

 

정답 코드

def solution(triangle):
    answer = []
    getlist = triangle.pop(0)
    while len(triangle) > 0:
        tmp = triangle.pop(0)

        for i in range(len(tmp)):
            if i == 0 or i == len(tmp) - 1:
                if i == 0:
                    tmp[0] = tmp[0] + getlist[0]
                if i == len(tmp) - 1:
                    tmp[-1] = tmp[-1] + getlist[-1]
        
            else:
                tmp[i] = max(getlist[i-1],getlist[i]) + tmp[i]
                        
        getlist = tmp
    
    return max(getlist)

 

결국 원하는 것은 Max 값이다.라는 원천에서 나온 풀이법입니다. 각 층에서 각 인덱스 위치에서 얻을 수 있는 최댓값을 가지고 다음 층에 도착하거나 해당 층이 마지막층이라면 그 층에서 가장 높은 값을 가져오는 방법입니다.

 

부록.

그런데. 다른 개발자들은 어떻게 풀었는지 보기 위해 다른 사람의 풀이를 누른 순간

엄청난 풀이를 보게 되어 공유드립니다.

말도 안 됩니다.... 이걸 한 줄로....

가독성은 떨어질 수 있습니다만 이 문제를 한 줄로 압축할 수 있다는 사실에 놀랍습니다.

저만 놀란 게 아닌 거 같습니다. 무수한 댓글이..