문제
https://www.acmicpc.net/problem/1932
[ 문제 조건 ]
- 한 줄씩 내려가면서 합이 최대가 되는 경로 구하기
- 더해질 수 있는 값은 대각선 왼쪽 or 오른쪽
[ 해결순서 ]
- 누적 값이 더해질 배열을 0으로 초기화 해서 입력받은 배열의 길이와 같게 선언 및 초기화 ( 그냥 입력받은 배열에다가 계산해도 무관하다 )
- 예제를 분석하다 보니 가로 줄의 첫번째 값과 끝 값은 비교 대상이 없으므로 그냥 전 줄의 같은 인덱스 값을 더하면 되고,
- 처음, 끝을 제외한 인덱스 값들은 이제 대각선 왼쪽 or 오른쪽을 비교해서 더 큰 값을 현재 값에 더해준다.
- 그렇게 값을 누적시키면 맨 마지막 줄에 이제 여태까지 누적된 경우의 수가 배열에 저장
- 그 중 최대 값을 구해 출력한다.
[ 예제 풀이 ]
✏️한줄평
: 약간의 인덱스 번호 헷갈림에 조금 걸렸지만 그래도 비교적 다른문제에 비해 빨리 풀었다. DP를 풀다보니 조금 감이 온 걸까... 그래도 분류를 모르고 풀었다면 시간이 더 걸렸을 것 같다. 문제 분류없이 빨리 푸는 그날까지... Keep.... Go..ing...
코드
'알고리즘' 카테고리의 다른 글
[Python] 백준 11051 : 이항 계수 2 (0) | 2021.08.29 |
---|---|
[Python] 백준 1309번 : 동물원 (0) | 2021.08.27 |
[Python] 백준 1946 : 신입사원 (0) | 2021.08.23 |
[Python] 백준 9663 : N-Queen (0) | 2021.08.19 |
[Python] 백준 2468번 - 안전 영역 (0) | 2021.08.09 |