<aside> 🔥 백준 1932번 문제 링크

</aside>

<aside> 🔥 문제 정리

트리 모양의 정수 삼각형이 주어진다.

맨 위층에서부터 아래에 있는 수 중 대각선에 있는 수를 선택하여 내려올 때 최대가 되는 경로를

구하라.

#입력값
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

# 출력값
30

# 예시 트리화
   			7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

</aside>

<aside> 🔥 접근 방법

이 문제는 못풀었다. 다이나믹 프로그래밍의 핵심은 규칙을 찾아야 하는데,

생각보다 쉽지가 않다.

풀이의 접근 방법은 아래와 같다.

아래 방법대로 그려가다 보면 한가지 규칙을 발견할 수 있고 이는 점화식으로 활용할 수 있다.

(r, c) = max((r-1, c-1),(r-1,c))

</aside>

<aside> 🔥 코드 진행

1. 입력값을 가져와서 그래프를 만들어주고 memoization을 위해 memo를 추가한다.

   memo의 기본 값은 무한대로 설정해준다.

   with open('정수삼각형.text') as f:
       sys.stdin = f
       input = sys.stdin.readline
   
       n = int(input())
       tree = [list(map(int, input().split())) for _ in range(n)]
   
       INF = int(1e9)
       memo = [[INF] * (i + 1) for i in range(n)]
   

2. n-1, 0 을 시작점으로 잡아서 함수를 호출한다.

   # n-1, 0 부터 시작
   for col in range(n):
       dp(n - 1, col)
   

3. 위 접근 방법에서 찾았던 점화식을 사용해서 재귀 함수로 사용한다.

   def dp(r, c):
       # r, c가 범위에 있지 않으면 0 리턴
       if not (0 <= r < n and 0 <= c < len(tree[r])):
           return 0
   
       # 이미 메모에 값이 있으면 그대로 값 리턴
       if memo[r][c] != INF:
           return memo[r][c]
   
       # 점화식 적용
       memo[r][c] = tree[r][c] + max(dp(r - 1, c - 1), dp(r - 1, c))
       return memo[r][c]
   

</aside>