[BOJ] 백준 1932번 : 정수 삼각형

백준 1932번 : 정수 삼각형

 

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

 

 

 

코드

 

경로를 따라가며 정수 삼각형의 해당 수를 선택했을 때 선택된 수의 합을 저장하는 dp 2차원 리스트를 생성한다.

dp는 정수 삼각형의 크기와 같다. 

 

삼각형의 맨 위층은 정수 하나이므로 dp에 그대로 입력값을 저장한다.

삼각형의 두번째 층 부터 맨 아래 까지는 하나의 층에서 왼쪽부터 오른쪽으로 이동하며 dp값을 갱신한다.

 

하나의 층 내에서 가장 왼쪽 값(j = 0)은 대각선 위층의 오른쪽 값으로 부터만 선택 될 수 있다. dp에 위층의 대각선 왼쪽값은 존재하지 않음. 여기에 현재 선택된 수를 더해 dp에 저장한다.

마찬가지로 하나의 층 내에서 가장 오른쪽 값(j = i - 1)은 대각선 위층의 왼쪽 값으로 부터 선택 된다. dp에 위층의 대각선 오른쪽값은 존재하지 않음. 여기에 현재 선택된 수를 더해 dp에 저장한다.

하나의 층에서 가장 왼쪽과 오른쪽값을 제외한 사이의 수를 선택할 때는 위층의 대각선 왼쪽과 오른쪽에서 모두 선택될 수 있기 때문에 

위층의 대각선 왼쪽과 오른쪽 값 중 큰 값에 현재 선택된 수를 더해 dp에 저장한다.

 

반복문을 n번만큼 돌고 난후 dp의 가장 아래층의 값들 중 최대값을 출력한다. 

 

 

n = int(input())

dp = [[0] * i for i in range(n+1)]

for i in range(1, n + 1):
    lines = list(map(int, input().split()))
    if i == 1:
        dp[i][0] = lines[0]
    else:
        for j in range(i):
            if j == 0:
                dp[i][j] = dp[i - 1][j] + lines[j]
            elif j == (i - 1):
                dp[i][j] = dp[i - 1][j - 1] + lines[j]
            else:
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + lines[j]

print(max(dp[n]))