알고리즘 관련/SPOJ 썸네일형 리스트형 SPOJ)BATMAN2 문제:http://www.spoj.com/problems/BAT2/ 각 방의 가중치가 주어지고 두명의 사람이 이동을 한다. 한 사람은 1에서 부터 다른 한사람은 N에서 부터 이동할 때 겹치지 않는 경로로 가중치가 증가하는 순서대로 이동할 때 밟을 수 있는 방의 수의 최댓값을 출력하는 문제이다. 다이나믹 프로그래밍을 이용하여 dp[pos][x][y]의 정의를 1번부터 pos번 정점까지 확인 했을 때 한 사람은 x번 정점을 마지막으로 한사람은 y번 정점을 마지막으로 밟았다고 생각하면 점화식을 세울 수 있다. dp[pos][x][y]= max(dp[pos][a[pos]][y]+1, dp[pos][x][a[pos]]+1 , dp[pos][x][y]) 1234567891011121314151617181920212.. 더보기 이전 1 다음