농담곰담곰이의곰담농

1932 정수 삼각형

by 브이담곰

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

✔ 유형 : DP

✔ 문제 풀이: DP memorization 방식으로 2차원 배열에 작은 값의 결과부터 저장

 

 

문제 접근

 

 

DP 점화식

 

 

코드

import sys
input = sys.stdin.readline

# input 1
N = int(input()) # size of triangle

arr = list()
DP = [[0 for _ in range(N)] for _ in range(N)] # memorization

# input 2
for i in range(N):
    line = list(map(int, input().split()))
    
    arr.append(line)

# initial value
DP[0][0] = arr[0][0]

# level of the triangle
level = 0

# bottom-up
while(level < N-1):
    for i in range(0,len(arr[level])): # list of the level line
        DP[level+1][i] = max(DP[level+1][i], DP[level][i] + arr[level+1][i]) 
        DP[level+1][i+1] = max(DP[level+1][i+1], DP[level][i] + arr[level+1][i+1])
        
    
    level += 1
    
print(max(DP[level])) # 해당 라인에서 가장 큰 값 프린트

'Coding Test > Baekjoon' 카테고리의 다른 글

1464 1로 만들기  (0) 2024.08.07
1923 연속합  (0) 2024.08.06
9461. 파도반 수열  (0) 2024.07.31
2579 계단 오르기  (0) 2024.07.26
1700. 멀티탭 스케줄링  (0) 2024.07.25

블로그의 정보

농담곰담곰이의곰담농

브이담곰

활동하기