[AC] 2240 자두나무

출처 : https://www.acmicpc.net/problem/2240

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2240.cpp

이 문제 역시 DP로 풀 수있다. 처음에는 DFS가 될까? 생각하였지만 아무리 계산해봐도 시간복잡도에서 초과가 되어버린다. 왜냐면 T가 1000이기 때문에 DFS로는 가망성이 없다.

그럼 결국  DP인데, 매 초마다 최대값을 갱신하는 방식을 써야겠다. 

개인적으로 상당히 고생했던 DP이고 결국 풀지못하여 다른사람의 아이디어를 참조했다.

이 DP문제의 경우 숫자로 가지고있는 패턴은 당연히 없고(n이 몇일때 몇이다가 아니다.), 배열로 맞추는 패턴도 아닌것같기 때문이다.

정답자의 아이디어를 빌리면 다음과 같다.

1. 나무의 위치를 입력받음에 따라 스텝수에 따라 해당 위치값을 1씩 더해준다. (이동할수있는 만큼 계속 이동한다고 전제하면 현재 위치에서 얻은 값은 계속 가져갈수있다.)

2. 현재 위치에서 바로 전의 단계에서 옆나무의 포인트를 보고 큰값을 대입한다. (이동을 안 할수도있는것이다.)

3. 최종적으로 담겨있는 가장 큰 값을 출력한다.

참으로 심플한 아이디어이다.  이렇게하면 각 스텝별로 얻을수있는 최고점수를 바로 알 수있다. 정말 신박한 아이디어라고 생각한다.