[Python] 백준 1932 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

코드 작성

n = int(input())
dp = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    for j in range(i+1):  #i의 인덱스가 0부터 시작하므로 i+1번 해야함
        if j == 0:
            dp[i][j] += dp[i-1][j]
        elif j == i:
            dp[i][j] += dp[i-1][j-1]
        else:
            dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])
print(max(dp[n-1]))

코드  풀이

#1. 점화식

행을 i, 열을 j로 설정한다.

(1) j == 0일 때

  i번째의 j가 0의 숫자는 오로지 i-1번째의 j = 0밖에 올 수 없다.

(2) j == i일 때

  즉 j의 가장 끝에 있는 숫자는 오로지 i-1번재의 j-1의 숫자가 올 수 밖에 없다.

(3) 그 밖에 i 번째의 j에 올 수 있는 숫자는

  dp[i-1][j] 또는 dp[i-1][j-1]의 숫자 중에서 큰 수 이다.

 

#2. 초기값

  - n 이 1일때 i는 1개만 주어지고 그 때의 인덱스는 0, 즉 range의 범위는 1부터 n까지

  - j 의 for문에 대해서 range가 i의 범위인데, i가 0부터 시작하므로 i+1까지