문제링크 : https://www.acmicpc.net/problem/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]의 값들 중 최댓값이 최대 경로 값이 된다.
'백준 > Python' 카테고리의 다른 글
[백준] 26072 곰곰이와 시소 (python 파이썬) (0) | 2022.11.28 |
---|---|
[백준] 26071 오락실에 간 총총이 (python 파이썬) (0) | 2022.11.28 |
[백준] 1912 연속합 (python 파이썬) (0) | 2022.11.27 |
[백준] 9461 파도반 수열 (python 파이썬) (0) | 2022.11.27 |
[백준] 11659 구간 합 구하기 (python 파이썬) (0) | 2022.11.24 |