1932. [Python]정수 삼각형

1. 문제

 

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

1932번: 정수 삼각형

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• DP(다이나믹 프로그래밍)

 

3. 파이썬 코드

 

import sys
# 많은 인풋 처리
input = sys.stdin.readline

N = int(input())
# 숫자 저장할 리스트
num_list = []
# 숫자 저장
for _ in range(N):
    num_list.append(list(map(int,input().split())))
# 1 ~ N 까지 반복
for i in range(1,N):
    # i+1 까지 반복
    for j in range(i+1):
        # 양 끝점일 경우 한 경우의 수만 더함
        if j == 0:
            num_list[i][j] += num_list[i-1][j]
        elif j == i:
            num_list[i][j] += num_list[i-1][j-1]
        # 외의 경우 이전값 대각선 중 max 값 선택
        else:
            num_list[i][j] += max(num_list[i-1][j-1], num_list[i-1][j])
# 최종 계산된 결과에서 max 값 추출
print(max(num_list[-1]))

 

4. 문제를 풀고난 후 생각

 

• 문제 자체가 굉장히 직관적인 문제로 양 끝점을 제외한 부분에서 이전 값들의 max 값을 선택하는 방식으로 bottom-up 으로 쌓아나간다.
• DP 문제의 기본적인 능력을 확인하는 문제 같다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP(다이나믹 프로그래밍)