[BOJ/Python] 2096. 내려가기
📌 문제 https://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 📌 문제 접근 방법 처음엔 dfs를 사용해서 최소값, 최대값을 갱신시켰는데 숫자가 많아질수록 모든 숫자를 저장하는 자체에서 메모리 초과가 발생하는 것 같았다. 따라서 입력 숫자를 저장하지 않고 입력받자마자 바로 사용할 수 있도록 dp를 사용해서 구현했다. 아래줄의 입장에서 0번째 숫자는 윗줄의 0, 1번째 숫자를 더할 수 있고, 1번째 숫자는 윗줄의 모든 숫자, 2번째 숫자는 윗줄의 1, 2번째 숫자를..
2021. 12. 8.