곧죽어도 콛잉

https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 기본적인 dp 문제! 먼저 시간복잡도만 계산해보면 100개의 구간 각각이 2개씩 가능하므로, 2^100이라는 큰 수가 나온다. 따라서 DP를 써야할 수 밖에 없다. 그래프를 진행할수록 반드시 필요한 2가지 상태값이 있다. 1. 현재 구간 위치 2. 지금까지의 소요시간 이것을 바탕으로 해당 경로가 가질 수 있는 최대값을 유추할 수 있다. 다음처럼 그래프를 그..