djm03178   1년 전

건설하는 다리들은 반드시 일직선의 형태여야 합니다.

예를 들어 공식 데이터에 아래와 같은 케이스가 포함되어 있는데, 일직선이 아닌 다리를 허용한다면 시작점과 끝점을 직접 149개의 다리로 이어 본래 경로의 길이 (3029.697... + 3014.143...)을 상쇄하여 5894.84 미터를 줄이는 것이 가능하지만, 일직선의 다리만을 허용할 경우 시작점과 끝점을 직접 잇는 것이 불가능하기 때문에 적어도 한 쪽 끝은 선분 중간에 이어줘야 하고, 그 경우 최적의 답은 5893.23 미터가 됩니다.

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