boj.kr/1932 정수 삼각형 (silver1) 파이썬 풀이

1. 삼각형의 크기 N이 1이면 첫번째 줄의 첫번째 수를 출력한다.

2. 그렇지 않다면, dp 리스트를 N개의 리스트로 초기화한다.

3. dp 리스트의 0번째 리스트로 삼각형의 첫번째 줄을 저장한다.

4. dp 리스트의 1번째 리스트로 삼각형의 두번째 줄의 각 수에 첫번째 줄의 수를 더한 리스트를 저장한다.

5. N 이 2라면, dp 리스트의 1번째 리스트의 두 수 중 큰 수를 출력한다.

6. N 이 2보다 크면, 아래를 dp 리스트의 마지막 요소까지 반복한다.

6.1. dp 리스트의 i번째 요소로 정수 리스트를 입력받아 저장한다.

6.2. dp 리스트의 i번째 리스트를 순회하면서 아래 6.2.1. ~ 6.2.3. 을 반복한다.

6.2.1. 0번째 요소이면, 0번째 요소에 이전 리스트의 0번째 요소를 더한 값을 저장한다.

6.2.2. 마지막 요소이면, 마지막 요소에 이전 리스트의 마지막 요소를 더한 값을 저장한다.

6.2.3. 0번째나 마지막 요소가 아니라면, 이전 리스트의 j 번째 값과  j-1번째 값 중 더 큰 값을 더한 값을 저장한다.

7. dp 리스트의 마지막 리스트 중 가장 큰 값을 출력한다.

 

N = int(input())
dp = [[] for _ in range(N)]

if N == 1:
    print(int(input()))
else:
    dp[0] = list(map(int, input().split()))
    dp[1] = list(map(int, input().split()))
    dp[1][0] += dp[0][0]
    dp[1][1] += dp[0][0]
    if N == 2:
        print(max(dp[1][0], dp[1][1]))
    else:
        for i in range(2, N):
            dp[i] = list(map(int, input().split()))
            for j in range(len(dp[i])):
                if j == 0:
                    dp[i][j] += dp[i-1][j]
                elif j == len(dp[i])-1:
                    dp[i][j] += dp[i-1][len(dp[i-1])-1]
                else:
                    dp[i][j] += max(dp[i-1][j-1], dp[i-1][j])

        print(max(dp[N-1]))

 

dp[y][x] 를 삼각형의 y번째 줄의 x번째 수를 선택하는 경우의 누적값 중 최대값으로 저장할 수 있다.