2096번: 내려가기 www.acmicpc.net 이 문제는 첫 줄에 적혀 있는 세 개의 숫자 중 하나를 골라 시작해 다음 줄로 내려갈 때마다 현재 수와 붙어 있는 수로만 이동할 수 있다는 조건 하에 마지막 줄까지 내려왔을 때 위치했었던 곳의 수의 합의 최댓값과 최솟값을 구하는 문제이다. 이는 dynamic programming을 이용하면 쉽게 해결할 수 있다. 두 번째 줄부터 첫 번째 칸은 이전 줄의 첫 번째 칸과 두 번째 칸을 통해 도달 가능하므로 두 가지 경우 중 최대 또는 최소가 되는 경우를 고르면 되고, 두 번째 칸은 이전 줄의 세 개의 칸 중에 고르면 되며, 세 번째 칸은 이전 줄의 두 번째 칸과 세 번째 칸 중에서 고르면 된다. 이를 마지막 줄까지 한 뒤에 마지막 줄의 결과 중 최대 또는 최..