[백준 BOJ] 1932 정수 삼각형 python

 

 

목차

• 1. 문제
• 2. 알고리즘 선택 이유
• 3. 접근방법
• 4. 코드

1. 문제

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

1) 문제

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

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

2) 입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

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

 

4) 출력예시

2. 알고리즘 선택 이유

정수에 순차적으로 탐색하면서 이전 행에서 계산한 값을 사용하기 때문에 dp를 사용하여 계산 정보를 저장해두고 불러와서 현재의 값과 연산을 하는것이 효율적인듯

3. 접근방법

입력된 삼각형을 순회하며 현재 위치에서 이전 층의 왼, 오른쪽의 값 중 큰 값을 선택하여 합을 구한다. 이때 현재 위치의 값을 계산한 값으로 업데이트한다. 

• 대각선 왼쪽 값이 없는 경우 : j==0, 오른쪽 값이 없는 경우 : j==i, 왼오 대각선 값이 있는 경우 j != i
• j == 0인 경우 이전 층의  오른쪽 값만 더한다 
• j == 1 인 경우 이전 층의 왼쪽 값만 더한다
• j != i 인 경우 이전층의 왼오 값 중 큰 값과 더한다

마지막 층에서 가장 큰 값을 찾는다

 

4. 코드

import sys

n = int(sys.stdin.readline().strip())
dp = [list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)]

for i in range(1,n):
    for j in range(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[-1]))