백준: 1932 정수 삼각형

문제

1932번: 정수 삼각형

 

문제 풀이

 삼각형의 특성을 이해하면 쉽게 풀 수 있는 문제이다. 삼각형 좌/우측 변에 있는 값들은 위의 값 중 하나의 값만 더하면 되지만 각 끝 변이 아닌 경우는 2개의 값을 받게 된다. 따라서 좌/우측 변을 제외하고 나머지는 가장 큰 값을 누적해주면 문제를 풀 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    triangle =\
        [list(map(int, stdin.readline().split())) for _ in range(n)]

    for i in range(1, n):
        for j in range(i + 1):
            # 가장 좌측인 경우
            if not j:
                triangle[i][j] += triangle[i - 1][j]
            # 가장 우측인 경우
            elif j == i:
                triangle[i][j] += triangle[i - 1][j - 1]
            # 중간에 위에 2개의 값을 비교하여야 하는 경우
            else:
                triangle[i][j] += \
                    max(triangle[i - 1][j], triangle[i - 1][j - 1])

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