[백준-1932] 정수 삼각형

이말감·2022년 4월 30일
0

백준

목록 보기
39/49

문제

링크

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * sum([i for i in range(1, n+1)])
arr = []

for _ in range(n) :
    arr += list(map(int, input().split()))

dp[0] = arr[0]
start = 0
for i in range(n-1) :
    for j in range(start, start+i+1) :
        dp[j+i+1] = max(dp[j] + arr[j+i+1], dp[j+i+1])
        dp[j+i+2] = max(dp[j] + arr[j+i+2], dp[j+i+2])
    start += i+1
    
print(max(dp))


문제는 위 사진과 같은 방법으로 풀었다.
일단 다 입력을 받아서 하나의 배열에 넣은 다음 삼각형 꼭대기에서 대각선 왼쪽, 오른쪽에 값을 넣어준다.

어떻게 문제를 풀어야 할지 생각하는 과정은 짧았지만 구현하는 데 오래 걸렸다.
정신차리고 풀자!

profile
전 척척학사지만 말하는 감자에요

0개의 댓글