99클럽 코테 스터디 8일차 TIL(dp)

📎 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

🤔 문제 이해 및 알고리즘 유형

알고리즘 유형

dp

💡 문제 해결 방법

정말 전형적인 dp 문제이다.

1) triangle을 처음부터 돌면서 아래로 내려갈 수록 누젹합을 저장해준다.

1-1) 처음과 마지막 값은 위에 있는 값을 누적으로 더해준다.

1-2) 가운데 있는 값은 j-1, j 의 값을 비교해서 누적합이 더 큰값으로 더해준다.

2) triangle의 마지막 줄에 다다르면 배열 중 가장 누적합이 큰 수를 출력한다.

💻 코드

def solution(triangle):
    answer = 0
    for i in range(1,len(triangle)):
        for j in range(len(triangle[i])):
            if j==0:
                triangle[i][j]+=triangle[i-1][j]
            elif j==len(triangle[i])-1:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                result= max(triangle[i-1][j-1]+triangle[i][j],triangle[i-1][j]+triangle[i][j])
                triangle[i][j]= result
    answer= max(triangle[-1])
    return answer

👍 이전에 작성했던 코드

def solution(triangle):
    answer=0
    m = len(triangle)
    for i in range(1,m):
        for j in range(i+1):
            if j==0: #왼쪽 계산
                triangle[i][j] += triangle[i-1][j]
            elif j==i: #오른쪽 계산
                triangle[i][j]+= triangle[i-1][j-1]
            else: #가운데 계산
                triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
                
    return max(triangle[-1])

 

이전에 작성했던 코드가 더 깔끔해서 같이 올린다.