yukariko   2년 전

나름 머리를 써봤는데 현재위치에서 아직 도착하지않은 다른 위치로 가는 최소값을 찾는 형식의 

그리디 밖에 떠오르질 않네요.. 첫번째 예제는 그걸로 정답이 뜨지만 두번째에서부터 막히네요.

어떤 방법이 있는지 힌트좀 부탁드립니다.

sujin   2년 전

..

yukariko   2년 전

헉 위키가 있었구나.. 감사합니다!

pl0892029   2년 전

문제 풀면서 관찰했던 것들을 적어놨었네요. 이 3가지 정보로 풀었었습니다.

1. [i,j] 구간을 고려할 때 항상 [i,j]에 있는 모든 원소를 포함하는 것이 이득이다.

2. [i,j] 구간을 고려할 때 항상 마지막에는 i 또는 j 위치에 있는 것이 이득이다.

3. 편의상 1번째 점부터 n번째 점까지 순차적으로 방문하는 것이 최적이라 가정하고, i번째 점과 i+1번째 점 사이의 거리를 Di라 하면, 최적의 값은 sum( (n-k)*Dk ) 이다. (k : 1..n-1)

댓글을 작성하려면 로그인해야 합니다.