[이코테] 다이나믹 프로그래밍 - 정수 삼각형 python

난이도 : ●◐○ | 풀이 시간 : 30분 | 시간 제한 : 2초 | 메모리 제한 : 128MB | 기출 : IOI 1994년도

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

 

문제

• 맨 위층부터 대각선 왼쪽 아래 또는 대각선 오른쪽 아래의 숫자 중 하나를 선택한다.
• 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.

 

입력조건

• 첫째 줄에 삼각형의 크기 n(1<=n<=500)이 주어진다.
• 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력조건

• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다,

 

입력예시

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력예시

30

 

아이디어

• 입력되는 삼각형의 값을 2차원 배열에 저장한다.
• 위에서 내려오면서 합을 구하는 것이니 마지막행에서 최대값이 나온다.
• 1번째 행부터 오른쪽 위의 수에게 선택당했을 때와, 왼쪽 위의 수에 선택되었을 때 중 최대값인 걸 구한다.
  • i가 1에서 n-1까지
    • j가 0에서 i까지일 때
      
      • j==0일 때 왼쪽 위에게 선택되는 경우는 없다.
      • j==i일 때 오른쪽 위에게 선택되는 경우는 없다.

 

코드

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int,input().split())))
    
for i in range(1,n):
    for j in range(i+1):
        if j==0:
            left_up = 0
        else:
            left_up = dp[i-1][j-1]
        if j==i:
            right_up=0
        else:
            right_up = dp[i-1][j]
        dp[i][j] = max(left_up, right_up)+dp[i][j]

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