[Python][백준 BOJ Silver I] 1932. 정수 삼각형 : DP

접근 방식

2024.03.02 - [Algorithm & Data structure/이론] - Dynamic Programming : DP, 동적 계획법, 다이나믹 프로그래밍

Dynamic Programming : DP, 동적 계획법, 다이나믹 프로그래밍

일단 하향식으로 코드를 작성해야겠다고 생각했다.
처음엔 메모이제이션을 위한 리스트를 아래 솔루션과는 다르게 별도로 만드려고 했는데 너무 복잡했다.
결국 1시간쯤 끄적이다 다른 분들의 솔루션을 보고 로직을 세웠다.
 
입력값을 담은 리스트에 그대로 메모이제이션한다.

✅Solution

import sys
n = int(sys.stdin.readline().strip())
num = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            num[i][j] += num[i-1][j]
        elif j == i:
            num[i][j] += num[i-1][j-1]
        else:
            num[i][j] += max(num[i-1][j], num[i-1][j-1])

print(max(num[n-1]))

위에서부터 아래로 값을 더하면서 내려오고, 맨 아랫줄에서 가장 큰 값을 출력하면 된다.
 
입력값이 담긴 리스트에 위→아래로 내려오며 더한 값을 업데이트해준다.
 
왼쪽으로만 쭉 내려오는 경우(j == 0), 오른쪽으로만 쭉 내려오는 경우(j == i)에는 다른 루트로 해당 숫자에 접근할 수 없으나,
이외의 경우엔 여러 루트가 하나의 수에 접근할 수 있다. 이럴 경우 이미 구해진 값(합)이 바뀔 수 있는데, 가장 큰 값을 출력해야 하므로 기존값과 변경값 중 큰 값이 저장되도록 한다.

---

오랜만!
나만무를 다 해치우고 다시 알고리즘 풀러 돌아왔어요.
이제 본격적으로 취업전선에 뛰어들게 되어 코테 언어를 자바스크립트로 바꿔야 하나 고민 중입니다.
한 달 반 만에 푸는 터라 파이썬조차 낯설어서 일단 하던 데로..... 파이썬으로 열심히 풀어보려 합니다.
끠야악
나만무 정리는 언제 하지?
정글에서 배운 것들 정리는 .............. ?
 
https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형