[BOJ][⚪1][백준#01932] 정수 삼각형

문제 출처

BAEKJOON Online Judge #1932

문제

    7
  3   8
8   1   0   2   7   4   4 4   5   2   6   5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제

입력

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

출력

30

My Sol

import sys
input = sys.stdin.readline

N = int(input())
mat = [list(map(int, input().split())) for _ in range(N)]
iv = mat[0][0]
if N == 1:
    print(iv)
    quit()

for j in range(2):
    mat[1][j] += iv

if N == 2:
    print(max(mat[1]))
    quit()

k = 2
while k < N:
    mat[k][0] += mat[k-1][0]

    for j in range(1, k):
        mat[k][j] += max(mat[k-1][j], mat[k-1][j-1])

    mat[k][k] += mat[k-1][k-1]
    k += 1

print(max(mat[N-1]))

DP를 이용하는 문제이지만, 배열을 덮어씌우며 삼각형의 가장 아랫단까지 가게 되면, 최하단의 최댓값을 구해 출력하였다. 이때 양쪽 바깥만 윗단의 왼쪽과 바로 위의 값의 최댓값을 현재 값에 더한다는 비교 공식이 통하지 않고, 자체적으로 위의 값이나 왼쪽 값만을 더하므로, 이 경우를 제외하기 위해, N이 1과 2일 때 사전적으로 걸러주었고, 3부터도, while문 내부에서 범위를 나누어 양쪽 끝은 자체적으로 값을 지정하였다.

결과

맞았습니다!!

모범답안

출처

import sys

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

for i in range(n-2, -1, -1):
    for j in range(i + 1):
        triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])

print(triangle[0][0])

코드가 유독 짧은 풀이가 있어서 분석해보겠다. 나는 위에서부터 아래로 내려오는 방식을 선택했는데, 이 분은 아래부터 더해 올라가는 방식을 사용하였다. 예외처리를 하지 않아도 돼서 상당히 획기적인 풀이인 것 같다.