[ 프로그래머스 / PYTHON ] 정수 삼각형

🖐 이 문제를 풀기전 워밍업으로 풀기 좋은 것
프로그래머스 lv2 땅따먹기

문제 설명

정수 삼각형

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

풀이 & comment

내가 어제 푼 땅따먹기와 같은 방식으로 살짝 바꿔서 총 5분 안에 코드를 다 짜고난 후 정확성 테스트가 다 맞을때 까지는 내가 그래도 어제 배운걸 까먹진 않는 사람시키구나 했는데 난 하나만 알구 둘은 모르는 사람시키였던 거시다..
짧은 좌절

그냥 3번째 for 문에서 굳이 len(dp)만큼 돌 필요없이 대각선 방향으로 거리가 1이므로 최대 2번만 돌면 되는 거여따. 인덱스가 넘어가는 것만 보정해주는 코드만 추가하면 된다.

그리고 좀 더 좋은 코드로 아래부터 올라가는 방법이 있다. 난 귀찮아서 안해따. 아마 이 방법이 시간이 덜걸릴걸?

코드

시간초과 코드

def solution(triangle):
    dp = triangle[0]
    for t in range(1,len(triangle)):
        temp = triangle[t]
        for cur in range(len(triangle[t])):
            max_ = 0
            for bef in range(len(dp)):
                if cur == bef or cur == bef + 1:
                    max_ = max(max_,dp[bef])
            temp[cur] = max_ + triangle[t][cur]
        dp = temp[:]
    return max(dp)

맞춘코드

def solution(triangle):
    dp = triangle[0]
    for t in range(1,len(triangle)):
        temp = triangle[t]
        for cur in range(len(triangle[t])):
            max_ = 0
            for bef in range(cur-1,cur+1):
                if bef == -1:   
                    max_ = dp[0]
                elif bef == len(dp):
                    max_ = dp[-1]
                else:
                    max_ = max(max_,dp[bef])
            temp[cur] = max_ + triangle[t][cur]
        dp = temp[:]
    return max(dp)