[Python] 백준 1932 정수 삼각형

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

1932번: 정수 삼각형

 

# 1932 정수 삼각형

N = int(input())
numbers = [list(map(int, input().split())) for _ in range(N)]

dp = [0] * N
dp[0] = numbers[0][0]

for level in range(1, N):
    for i in range(level, -1, -1):
        if i == 0:
            dp[i] = dp[0] + numbers[level][i]
        else:
            dp[i] = max(dp[i], dp[i - 1]) + numbers[level][i]

print(max(dp))

 

 

dp를 사용하여 문제를 풀었다.

이중 리스트를 리스트 한 개로 줄였다고 생각하면 편하다.

 

for i in range(level, -1, -1)에서 역순으로 탐색하였다.

역순으로 탐색하지 않으면, 같은 행에서 이전의 연산이 다음 연산에 영향을 주기 때문에 역순으로 탐색하였다.

 

맨 처음엔 요렇게 풀었다가, 위처럼 최적화하였다.

 

# 1932 정수 삼각형

N = int(input())
numbers = list()
for _ in range(N):
    num = list(map(int, input().split()))
    numbers.append(num)

dp = [0] * N
dp[0] = numbers[0][0]
if N >= 2:
    dp[1] = dp[0] + numbers[1][1]
    dp[0] = dp[0] + numbers[1][0]

for level in range(2, N):
    for i in range(level, -1, -1):
        if i == level + 1:
            dp[i] = dp[i - 1] + numbers[level][i]
        elif i == 0:
            dp[i] = dp[0] + numbers[level][i]
        else:
            dp[i] = max(dp[i], dp[i - 1]) + numbers[level][i]

print(max(dp))