[프로그래머스] [Level 3] [DP] 정수 삼각형

정수 삼각형

프로그래머스

 

• 내 풀이
  • 인덱스 에러

import math

def solution(triangle):
    answer = 0
    n=len(triangle)
    #dp 테이블
    d=[[0 for j in range(i+1)] for i in range(n)]
    d[0]=triangle[0]
    
    for i in range(1, n):
        for j in range(i+1):
            if j==0 or j==i:
                d[i][j]=triangle[i][j]+d[i-1][j]
            elif j==1:
                d[i][j]=triangle[i][j]+max(d[i-1][0],d[i-1][1])
            elif j%2==0:
                d[i][j]=triangle[i][j]+max(d[i-1][j//2],d[i-1][j//2+1])
            elif j%2!=0:
                d[i][j]=triangle[i][j]+max(d[i-1][math.ceil(j/2)],d[i-1][math.ceil(j/2)+1])
                
    return max(d[n-1])

 

• 다른 사람 풀이
  • 인덱스 주의해서 보기!!! 
  • j==i 일때 d[i-1][j-1] 에 넣어야 한다.
    • -> 1열 전의 마지막 인덱스는 하나 작기 때문
  • 짝홀 나눌 필요 없이 d[i-1][j-1], d[i-1][j] 중 큰 값 더하면 됨

import math

def solution(triangle):
    answer = 0
    n=len(triangle)
    #dp 테이블
    d=[[0 for j in range(i+1)] for i in range(n)]
    d[0]=triangle[0]
    
    for i in range(1, n):
        for j in range(i+1):
            if j==0:
                d[i][j]=triangle[i][j]+d[i-1][j]
            elif j==i:
                d[i][j]=triangle[i][j]+d[i-1][j-1]
            else:
                d[i][j]=triangle[i][j]+max(d[i-1][j-1],d[i-1][j])
    return max(d[n-1])