2017/08/19 썸네일형 리스트형 BOJ)10272 현상금 사냥꾼 김정은 문제:icpc.me/10272 왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다. 이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다. 우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다. 점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #inc.. 더보기 이전 1 다음