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 |
블로그의 정보
농담곰담곰이의곰담농
브이담곰