내려가기
-
[BOJ]백준 2096번: 내려가기/DPProblem Solving/BOJ(백준) 2020. 12. 26. 02:11
www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 정의 N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다. 단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다. 2. Recursion&Subproblem K-1번째 줄에서 1번을 선택했다면 K번째 줄에서 1, 2번 중 큰 숫자를 선택한다 K-1번째 줄에서 2번을 선택했다면 K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다 K-1번째 줄에서 3번을 선택했다면 K번째 줄에서 2,3번..