BOJ/백준-1932-python

문제📖

풀이🙏

• 첫째 줄에 삼각형의 크기 n(1 <= n <= 500)이 주어지고, 둘때 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
• 맨 위층부터 시작하여 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라.
• 아래층에 있는 수는 현재층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
• 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력하라.
• DP 알고리즘 문제이다.
• dp는 큰 문제를 작은 문제로 나누어서 풀 수 있으며 처음에 단계를 배열로 할당한 뒤, 각 단계를 비교하는 방식에 수월하다.

코드💻

# boj, 1932 : 정수 삼각형, python
# dp : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
import sys

def DP(triangle):
    for i in range(1, n): 
        for j in range(len(triangle[i])): 
            if j == 0:
                triangle[i][j] = triangle[i-1][j] + triangle[i][j] 
            elif j == len(triangle[i]) - 1: 
                triangle[i][j] = triangle[i-1][-1] + triangle[i][j] 
            else:
                triangle[i][j] = max(triangle[i-1][j-1], triangle[i-1][j]) + triangle[i][j] 
    return max(triangle[n-1])

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

print(DP(triangle))

결과😎

출처 && 깃허브📝

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