[python] 백준 - 정수 삼각형(1932)

요즘 dp를 공부하기 시작하면서

백준 문제를 풀기 시작했다.

 

프로그래머스에서만 문제를 풀다가

오래간만에 input부터 다시 받으려 하니

은근히 헷갈리는 부분이 많다.

 

여하튼 오늘은 백준의 정수 삼각형이라는

간단한 dp 문제를 들고 왔다.

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

1932번: 정수 삼각형

 

정수 삼각형은

간단하지만 dp의 개념을 잘 보여준 문제라고 생각한다.

 

1. 아이디어

 

현재 자신의 위치를 기준으로

좌상단 우상단

데이터 중 큰 데이터를 더해가며

나올 수 있는 가장 큰 값을 구하는 문제다.

 

2. 코드

 

import sys
input = sys.stdin.readline 
 
N = int(input())
 
# 삼각형 데이터를 받고 값을 더해주며 확인해갈 배열
dp = [list(map(int, input().split(" "))) for _ in range(N)]
 
for i in range(1, N):
    for j in range(len(dp[i])):
        left = 0
        right = 0
        # 좌상단 데이터
        if j-1 >= 0:
            left = dp[i-1][j-1]
        # 우상단 데이터
        if j < len(dp[i-1]):
            right = dp[i-1][j]
        # 현재 삼각형 데이터 + 좌상단, 현재 삼각형 데이터 + 우상단 데이터 중 큰 값으로 업데이트
        dp[i][j] = max(dp[i][j] + left, dp[i][j] + right)
 
print(max(dp[N-1]))