1932. 정수 삼각형

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

이해

• 완전 탐색을 통해 모든 경우의 수를 확인하는 방식을 사용할 수 있지만, 삼각형의 크기가 1~500 이기 때문에 완전 탐색을 할 경우 시간 초과가 날 수 있다.(2^500가지 경우의 수)
• 따라서 동적 계획법이용하여 시간을 줄여야 한다.

구현

• 동적 계획법(DP, Dynamic Programing 이하 DP)을 사용하되, 기본적인 풀이 방식이 아닌 입력을 받은 후, 입력받은 배열을 변경하는 식으로 구현
• 문제에 있는 크기 5의 정수 삼각형을 예시로 들어보자

i/j	j=0	j=1	j=2	j=3	j=4
i=0	7	0	0	0	0
i=1	3	8	0	0	0
i=2	8	1	0	0	0
i=3	2	7	4	4	0
i=4	4	5	2	6	5

1. i=0일 때는 Pass(비교할 수 없음)

   i/j	j=0	j=1	j=2	j=3	j=4
   i=0	7	0	0	0	0
   i=1	3	8	0	0	0
   i=2	8	1	0	0	0
   i=3	2	7	4	4	0
   i=4	4	5	2	6	5

2. i=1일 때,
   1. j=0 → [1][0]으로 올 수 있는 경우의 수 👉[0][0]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	0	0	0	0
      i=2	8	1	0	0	0
      i=3	2	7	4	4	0
      i=4	4	5	2	6	5

   2. j=1 → [1][1] 으로 올 수 있는 경우의 수 👉[0][0]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	8	1	0	0	0
      i=3	2	7	4	4	0
      i=4	4	5	2	6	5

3. i=2 일 때.
   1.  j=0 → [2][0]으로 올 수 있는 경우의 수 👉[1][0]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	1	0	0	0
      i=3	2	7	4	4	0
      i=4	4	5	2	6	5

   2.  j=1 → [2][1] 으로 올 수 있는 경우의 수 👉[1][0], [1][1] 중 더 큰 수를 더함
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	0	0	0
      i=3	2	7	4	4	0
      i=4	4	5	2	6	5

   3.  j=2 → [2][2] 으로 올 수 있는 경우의 수 👉[1][1]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	2	7	4	4	0
      i=4	4	5	2	6	5

4. i=3 일 때.
   1.  j=0 → [3][0]으로 올 수 있는 경우의 수 👉[2][0]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	7	4	4	0
      i=4	4	5	2	6	5

   2.  j=1 → [3][1] 으로 올 수 있는 경우의 수 👉[2][0], [2][1] 중 더 큰 수를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	4	4	0
      i=4	4	5	2	6	5

   3.  j=2 → [3][2] 으로 올 수 있는 경우의 수 👉[2][1], [2][2] 중 더 큰 수를 더 해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	4	0
      i=4	4	5	2	6	5

   4.  j=3 → [3][3] 으로 올 수 있는 경우의 수 👉[2][2]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	4	5	2	6	5

5. i=4 일 때.
   1.  j=0 → [4][0]으로 올 수 있는 경우의 수 👉[3][0]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	24	5	2	6	5

   2.  j=1 → [4][1] 으로 올 수 있는 경우의 수 👉[3][0], [3][1] 중 더 큰 수를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	24	30	2	6	5

   3.  j=2 → [4][2] 으로 올 수 있는 경우의 수 👉[3][1] , [3][2] 중 더 큰 수를 더해줌  
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	24	30	27	6	5

   4.  j=3 → [4][3] 으로 올 수 있는 경우의 수 👉[3][2] , [3][3] 중 더 큰 수를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	24	30	27	26	5

   5.  j=4 → [4][4] 으로 올 수 있는 경우의 수 👉[3][3]를 더해줌
      

      i/j	j=0	j=1	j=2	j=3	j=4
      i=0	7	0	0	0	0
      i=1	10	15	0	0	0
      i=2	18	16	15	0	0
      i=3	20	25	20	19	0
      i=4	24	30	27	26	24

6. 마지막 배열 중 가장 큰 값을 출력 
   1. 답: 30

 

코드

# 1932 정수 삼각형
import sys
input = sys.stdin.readline


def solution(n:int)->int:
    triangle = [[0] * n for _ in range(n)]
    # 입력을 저장
    for i in range(n):
        tmp = list(map(int, input().split()))
        for j in range(i+1):
            triangle[i][j] = tmp[j]
    # i를 1~n 까지 돌리면서 최댓값만을 저장
    for i in range(1, n):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
	# 마지막 최댓값 반환
    return max(triangle[-1])


if __name__ == "__main__":
    n = int(input())
    print(solution(n))