[백준] 2096 내려가기

백준: 문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 처음에는 단순한 DP 문제인줄 알았는데, 메모리를 줄이는 게 관건인 문제였다. N의 최대 크기는 100,000으로 배열 크기를 그만큼 잡아야한다고 생각했다. 하지만 잘 생각해보면 직전 줄의 값만 필요하고 그보다 이전 줄의 값은 필요하지 않다. 따라서 이전 줄과 현재 줄의 값만 저장하면 되므로 long long dp[2][3]만 있으면 된다. 경우의 수 dp 배열의 크기를 줄여도 여전히 메모리를 줄이라는 경고 문자가 뜬다. 즉 주어진 입력값을 저장하는 배열조차도 줄..

2021.10.07