[백준 1932 정수삼각형][Python] -DP 연습!

[ 정의 ]

한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 한다.

작은 부분으로 큰 것을 계산 한다고 이해 하면 된다!

다이나믹 프로그래밍은 점화식을 코드로 옮겨서 구현할 수 있다.

 

[ 방법 ]

 

1. 탑다운 방식

- 재귀 함수를 이용해 큰 문제 해결을 위해 작은 문제를 호출

 

2. 보텀업 방식

- 반복문을 통해 작은문제 해결 후 이를 모아 큰 문제를 해결

 

[ 예시 문제 ] 

 

문제

        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

 

코드 풀이

 

n = int(input())
tr = []
for _ in range(n):
    a = list(map(int, input().split()))
    tr.append(a)

for i in range(n):
    for j in range(i+1):
    	# 처음 행이면 본인이다.
        if i == 0:
            tr[i][j] = tr[i][j]
            continue
        # 첫 열이면 위의 것만 받아온다.
        if j == 0:
            up = tr[i-1][0]
            tr[i][j] += tr[i-1][0]
            continue
        # 마지막 열이면 왼쪽 것만 받아온다.
        if j == i :
            left = tr[i-1][j-1]
            tr[i][j] += tr[i-1][j-1]
            continue
		# 두 쪽에서 받아오면 두 개 중 큰것을 받아와서 저장한다.
        else:
            up_left = tr[i-1][j-1]
            up_right = tr[i-1][j]
            tr[i][j] += max(up_left, up_right)

result = 0
for j in range(n):
    result = max(result, tr[n-1][j])
print(result)

DP의 해결방식대로 두 개의 수 중 큰 것을 선택해 내려오는 방식으로 풀이해줬다.

DP는 그림을 그리면 해결하기에 더 쉽다!
차근차근 익혀서 어려운 DP 문제도 잘 풀어나가봐야지.