[Python] 백준1932 정수 삼각형

19 May 2023 in Study on Algorithm

백준1932 정수 삼각형 링크

문제

예제 입력

---

코드

import sys

n = int(input())
arr = [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [ [0] * (x+1)  for x in range(n)]
dp[0][0] = arr[0][0]

for i in range(1, n): # 1 2 3 4

    for j in range(i): # 1번 / 2번 / 3번 / 4번
        if  dp[i][j] < dp[i-1][j] + arr[i][j]:
            dp[i][j] = dp[i-1][j] + arr[i][j]

        if  dp[i][j+1] < dp[i-1][j] + arr[i][j+1]:
            dp[i][j+1] = dp[i-1][j] + arr[i][j+1]

print(max(map(max, dp)))

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 정수 삼각형를 구현했습니다.

---

정리

n = int(input())
arr = [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]

def sol(st, num, sum):
    global ans
    if st == n:
        if ans < sum:
            ans = sum
        return

    sol(st+1, num, sum+arr[st][num])
    sol(st+1, num+1, sum+arr[st][num])

ans = 0
sol(0, 0, 0)
print(ans)

처음에는 재귀함수로 시간초과가 발생했습니다.

---

결과