[백준1932] / 정수 삼각형 - DP

 

백준1932

 

 

푼 날짜 : 2024.08.03

푼 문제 : [1932] / 정수 삼각형

사용한 언어 : python

알고리즘 : DP

 

 

점화식:

dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+lst[i][j]

 

 

*주의)

첫 번째 요소에는 dp[i-1][0]만 더할 수 있다.

마지막 요소에는 dp[i-1][j]를 더할 수 없다.

=> 둘 다 index error 가 발생하므로 두 부분은 따로 작성해주었다.

 

 

 

(내)이해를 돕기위한 그림

 

일단 이렇게 그림을 그려 이해했다.

머리로 생각하는 삼각형 구조와 입력값으로 주어지는 배열의 인덱스를 이해하기 위해 둘 다 그림으로 그렸다.

 

 

 

코드로 출력했을 땐,

 

출력

 

첨부 이미지처럼 나온다.

 

 

 

코드:

import sys

N = int(sys.stdin.readline())
lst = []
for _ in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    lst.append(row)

if N == 1:
    print(lst[0][0])
else:
    dp = [[0]*i for i in range(1, 500+1)] # 넉넉하게 N의 범위에 맞게 설정해주었다

    dp[0][0] = lst[0][0]
    dp[1][0] = dp[0][0] + lst[1][0]
    dp[1][1] = dp[0][0] + lst[1][1]

    for i in range(2, N):
        dp[i][0]=dp[i-1][0]+lst[i][0]
        for j in range(1, len(lst[i])-1):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+lst[i][j]
        dp[i][-1]= dp[i-1][-1]+lst[i][-1]
        
    print(max(dp[N-1]))

 

 

✨ 점화식 키포인트

 

현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

 

라는 말을 구현 방향성에 맞게 생각해보면,

계산하려는 층의 값 dp[i][j]은 이전 층의 dp[i-1][j-1]과 dp[i-1][j] 중 더 큰 수에 현재 값 lst[i][j]을 더하면 된다는 말과 같다.

 

따라서 i번째 줄의 값을 하나씩 반복할 때 i번째 줄의 첫 번째 요소와 마지막 요소만 예외처리를 해주었다.

 

 

---

 

처음에 

1
10

 

과 같은 N 이 1일 때의 경우를 생각하지 못하고 dp 테이블 초기값 설정을 해주면서 틀렸었다.

그래서 1일 때는 입력 받은 값을 바로 출력하고, 그렇지 않은 경우에는 dp 테이블을 만들어 계산을 진행하도록 수정했다.

 

 

---

비슷한 문제

 

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

프로그래머스