99클럽 코테 스터디 10일차 TIL 프로그래머스 정수 삼각형

프로그래머스 정수 삼각형

이 문제는 전형적인 DP문제다.

삼각형에 있는 경로들을 모두 따라가보면서 최대값을 갱신하고, 마지막 줄에 최대가 되는 값을 출력하면 되는 문제이다.

나의 코드1 (이전 코드)

 하나의 리스트에 계속해서 덮어쓰는 형식으로 진행했다.

def solution(triangle):
    mem=[0 for _ in range(len(triangle)+2)]
    for seq in range(len(triangle)):
        temp=[]
        for i in range(len(triangle[seq])):
            temp.append(max(mem[i],mem[i+1])+triangle[seq][i])
        for j in range(len(temp)):
            mem[j+1]=temp[j]
    return max(mem)

 

나의 코드2 (오늘 푼 코드)

똑같은 정삼각형 모양의 배열을 만들어 최대값을 구하는 방식으로 풀었다. 

def solution(triangle):
    dp=[[0 for _ in range(i)] for i in range(1,len(triangle)+1)]
    dp[0][0]=triangle[0][0]
    for j in range(1,len(triangle)):
        for k in range(j+1):          
            if k==0:
                left=0
                right=dp[j-1][k]
            elif k==j:
                left=dp[j-1][k-1]
                right=0
            else:
                left=dp[j-1][k-1]
                right=dp[j-1][k]
            dp[j][k]=max(left,right)+triangle[j][k]
    return max(dp[-1])

 

오늘의 회고

이 문제는 그래도 기본 DP 문제여서 빠르게 풀 수 있었던 것 같다. 

가독성은 코드2가 같은 삼각형이라 뛰어나지만 ,메모리 사용측면에서는 이전코드 1이 더 효율적인 코드였다.