[백준/이취코] 정수삼각형 1932 / DP / Python 실1

내가 이걸 1년 전에 왜 풀었을까...?

 

그땐 실력이 별로라서 독자적으로 풀진 않았을 듯 한데

오늘은 거의 뭐 15분컷? 했습니다

너무 자명한 문제죠

그림에 써진 웨에엑 << 졸음껌 너무 많이 먹어서 카페인 때문에 토하려고 하는거...

신경쓰지 마세요

 

무튼 이런 트리 구조의 정수 값을 입력 받고,

각 수들은 왼쪽 또는 오른쪽 대각선 값만 접근할 수 있습니다

 

이걸 다 입력받고 다시 처리할까?하다가 문득 실시간 처리가 가능하다는 생각이 들었어요

그래서 그림으로 그려봤습니다

 

누적 dp 배열과

현재 입력받은 배열 a가 존재한다고 생각해봅시다

 

일단 첫번재 배열 a에는 원소 하나만 있고, dp도 빈 상태니까

dp.append(a) 해주고 넘깁니다

 

그 다음부터 dp 점화식을 세워봅시다

 

배열 a의 가장 첫 번째 원소는 dp의 첫번째 원소와 더한 값이고

배열 a의 가장 마지막 원소는 dp의 가장 마지막 원소와 더한 값입니다

 

그 사이 관건은 두번째부터 len(배열a)-2번째 원소까지 처리입니다

그 범위 사이 원소들을 j번째라고 두면

배열 a의 j번째 원소는 누적dp배열의 j-1번째 원소를 더하거나, j번째 원소를 더한 값 중 max값을 저장하게 되어있습니다

최대 누적 합을 구해야 하기 때문이죠

 

그래서 이런 방식으로 계산을 돌리다보면 마지막 입력을 받은 후에는 가능한 누적 합의 값들이 저장되어 있을거고

그 중에서 max값이 최대의 최대일테니 max(dp)를 return하면 되겠네요

 

그걸 코드로 짜면 아래와 같습니다

 

n = int(input())

dp=[]
for i in range(n):
    if i==0:
        a = int(input())
        dp.append(a)
    else:
        a = list(map(int,input().split()))
        al = len(a)
        # print(a)
        # print(dp)
        new_dp=[]
        new_dp.append(dp[0]+a[0])
        for j in range(1,al-1):
            # print(j)
            new_dp.append(max(a[j]+dp[j-1],a[j]+dp[j]))
        new_dp.append(dp[-1]+a[-1])
        dp=new_dp
# print(dp)
print(max(dp))