[프로그래머스/python] Level 3 - 정수 삼각형 (DP)

프로그래머스

 

문제 해결을 위한 고민

얼핏 보고 DFS를 고려했으나, 삼각형의 높이가 500개라는 걸 보고 감이 왔다. 이건 DFS로 풀면 안된다고.

 

만약 DFS로 풀면 어떻게 될까? 경우의 수를 따져보면, DFS로 완전탐색하는데 걸리는 횟수는 1줄일 때 1번, 2줄일때 2번, 3줄일 때 4번, 4줄일 때 8번...이런 식으로 2^(n-1)가 된다.

 

500줄이면 2^499= 1,636,695,303,948,071,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

 

이 된다.

 

말도 안되는 숫자기 때문에 누구나 봐도 이건 불가능하다는 게 딱 보일거다.

 

코딩테스트에서 시간 복잡도를 따지는 건 엄청 중요하다. 대충 10^8=1초기 때문에, 필자가 항상 강조하는 for for이 1000을 넘어가는 테스트 케이스에서 쓰지 말라는 것도 이 때문이다.

 

따라서 처음엔 어떻게든 DP로 만들기로 했다. 그렇게 나온 코드가 위에서 아래로 내려가는 코드였다.

 

하지만 문제는, 위에서 아래로 내려가게 되면 더해주는 리스트가 한칸씩 늘어나야 한다는 것.

그래서 필자는 거꾸로 생각해서 풀었다. 아래에서 위로 올라가면 오히려 리스트가 한칸씩 줄어드니까.

 

풀이 코드

def solution(triangle):
    q=list(reversed(triangle))
    q.append(0)
    for i in range(len(q)-1):
        k1=q[i]
        k2=q[i+1]
        for j in range(len(k1)-1):
            dp=max(k1[j],k1[j+1])
            k2[j]+=dp

    answer = k1[0]
    return answer

 

위 코드는 아예 처음에 푼 코드.

복잡하기 때문에 조금 더 깔끔하게 변경한 코드는 다음과 같다.

def solution(triangle):
    h=len(triangle)
    q=triangle
    while h>1:
        for i in range(h-1):
            dp=max(q[h-1][i],q[h-1][i+1])
            q[h-2][i]+=dp
        h-=1
        
    answer = q[0][0]
    return answer

 

개념으로는 간단하다. 아래에 있는 리스트들에서, 양쪽의 숫자들을 비교해서 위에 있는 리스트에 더해주는 거다.

 

예를 들어 예제인 4,5,2,6,5와 그 위의 2,7,4,4가 있다면, 4와 5중 5 / 5와 2중 5 / 2와 6중 6 / 6과 5중 6을 택해서,

2+5,7+5,4+6,4+6 = 7,12,10,10 으로 만들어주는 작업을 반복한다.

 

그렇게 반복해서 어차피 맨 위로 가게 되면 딱 하나만 남는다. 그래서 딱히 리스트를 만들어 줄 필요는 없다.

 

이게 좀 헷갈릴 수 있는데, 간단하게 생각하면 된다. 합의 최대값을 비교연산해서 아래서부터 위로 올라간다고.

 

그렇게 생각해보면 다른 방식으로도 아주 쉽게 풀릴 것이다.