문제 설명
•
크기가 (N, M)인 2차원 배열에서 준규가 가져올 수 있는 사탕 개수의 최대값을 구하는 문제
예제 입력/출력
•
입력1
3 4
1 2 3 4
0 0 0 5
9 8 7 6
Plain Text
복사
•
출력1
31
Plain Text
복사
•
입력2
3 3
1 0 0
0 1 0
0 0 1
Plain Text
복사
•
출력2
3
Plain Text
복사
•
입력3
4 3
1 2 3
6 5 4
7 8 9
12 11 10
Plain Text
복사
•
출력3
47
Plain Text
복사
제약 조건
•
•
사탕의 개수
문제 풀이
•
준규가 (r, c)에 있다고 가정할 때, 이동할 수 있는 방향은 총 3가지
1.
(r+1, c)
2.
(r, c+1)
3.
(r+1, c+1)
•
풀이 1 브루트 포스
◦
모든 경우를 탐색하는 방법: 최대
•
풀이 2 그리디
◦
가장 높은 원소들을 선택해서 가는 방법 ≠ 최적해
풀이 3 DP (Bottom-Up)
풀이 4 DP (Top-Down)
풀이 코드
DP (Bottom-Up)
DP (Top-Down)
•
성능 비교 (Bottom-Up > Top-Down)
방식 | 메모리 | 시간 | 코드 길이 |
Bottom-Up | 78776 KB | 836 ms | 354 B |
Top-Down | 78944 KB | 2260 ms | 558 B |
알아두면 좋은 내용들
sys.setrecursionlimit