[백준] 1932 정수 삼각형 (python 파이썬)

문제링크 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

작성코드

 

 

 

풀이

 

1) 꼭대기부터 내려가면서 최댓값을 찾아야하는 문제이다.

        7
      3   8	
    8   1   0
  2   7   4   4
4   5   2   6   5

2) 내려가면서 해당 위치에 도달할 수 있는 최대값을 dp에 저장해주어 재활용 해준다.

※ 알아보기 쉽도록 dp 배치를 1번 입력과 동일한 형식으로 만들어주었다.

 

 

3) 가로줄에서 2차배열의 0과 세로줄과 같은 숫자의 경우는 선택지가 하나로 고정되어있다.

dp[h][0] = dp[h-1][0]

dp[h][h] = dp[h-1][h-1]

 

4) 가로줄 양쪽 끝을 제외한 중간 값들은 둘 중 큰 값을 선택하고 해당 줄 값을 더해준다.

dp[h][w] = max(dp[h-1][w-1], dp[h-1][w]) + num[h][w]

 

 

5) h(높이) 값의 경우 0번부터 시작하므로 N줄의 경우 dp[N-1]의 값들 중 최댓값이 최대 경로 값이 된다.