[백준 2024/03/21] 1932번 정수 삼각형

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

1932번: 정수 삼각형

 

1. 접근 방법

삼각형의 특정 위치에서의 삼각형 밑변까지 도달하기까지의 최댓값은 고정되어 있다고 생각하였다.

따라서 해당 위치에서의 최댓값을 memoization을 통해서 저장해둔다면, 값을 구할 수 있을 것이라 생각하였다.

 

따라서 만약 dictionary에 구하고자 하는 값이 있다면 그 값을 반환해 주었으며, 해당 dictionray에는 그 위치에서 얻을 수 있는 최댓값을 포함하고 있다.

 

만약, 밑변에 도달했다면, 더 이상 나아갈 길이 없기 때문에, 그 때는 자기 자신의 값을 반환해주었다.

 

dict_t[(a, b)] = triangle[a][b] + max(f(a + 1, b), f(a + 1, b + 1))

이런식으로, 현재 위치 값 + 왼쪽 오른쪽의 경우에서 최댓값을 더한 값을 dict[(a, b)] 의 최댓값이라 판단, 그 값을 memoization에 넣어주었다.

 

처음에는 잊고 triangle[a][b]를 더해주지 않아서, 값이 제대로 나오지 않았었다.

 

2. 코드

dict_t = {}


def f(a, b):
    if (a, b) in dict_t:
        return dict_t[(a, b)]
    if a == height - 1:
        return triangle[a][b]
    dict_t[(a, b)] = triangle[a][b] + max(f(a + 1, b), f(a + 1, b + 1))
    return dict_t[(a, b)]


height = int(input())
triangle = []
for i in range(height):
    sub_triangle = [int(n) for n in input().split()]
    triangle.append(sub_triangle)

print(f(0, 0))