[알고리즘] 내려가기 (백준 2096번)
2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍 문제다. 최소, 최대 값을 묻는 문제인데 이전에도 자주 풀어 본 적이 있는 유형이다. Solution 우선 max_dp와 min_dp로 나누어서 각각 최대값, 최소값을 구하는 dp 배열로 만든다. 여기서 최적화할 수 있는 방법은, 최대, 최소값을 구하기 위해서는 max_dp[i][3] 과 max_dp[i-1][3] 만 필요하면 되기 때문에 행이 2개만 있으면 된다. 그래서 max_dp, min_dp 에 필요한 원소 개수는 12개만 있으면 된다. N만큼 반복..
2020. 10. 29.
