내려가기
-
[백준]2096: 내려가기 - JAVA문제풀이/백준 2021. 4. 26. 15:09
[백준]2096: 내려가기 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 풀이 DP문제로 프로그래머스의 '정수 삼각형'문제와 매우 유사하다. 정수 삼각형은 최대값만 찾았다면 이번 문제는 최대, 최소값을 모두 찾는 문제이다. 합을 누적시킬때 최대값을 누적시키는 maxDp, 최솟값을 누적시키는 minDp배열을 만들어 주었다. 이때 한 줄당 총 3개의 숫자가 올 수 있으므로 3개의 경우로 나누어서 누적시켜주었다. 각각의 위치에서 누적시킬 인덱스는 다음과 같다. 현재 인덱스가 ..