BOJ 12549 Travel Plan (Small)

문제 링크:

문제 내용

일직선 위에 $N$개의 점이 있습니다. 각 점의 좌표는 정수입니다. 당신은 1번 점 위에 있으며, 1번 점의 위치는 0입니다.

당신은 다른 모든 점을 한 번씩 방문하고 1번 점으로 돌아오려고 합니다. 어떤 점을 방문하지 않고 지나칠 수도 있으나, 방향 전환(앞-뒤 또는 뒤-앞)은 어떤 점을 방문했을 때만 가능합니다.

그러한 방법들 중 총 이동 거리가 $F$ 이하이면서 가능한 한 최대인 것의 이동 거리를 구하세요.

입력

첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100$)

각 테스트 케이스에 대해, 첫 줄에는 점의 개수 $N$이, 두 번째 줄에는 각 점의 위치 $X_i$가 주어집니다. 모든 점의 위치는 서로 다르며, $X_1$은 0입니다. ($2 \le N \le 10$, $-10^{15} \le X_i \le 10^{15}$)

세 번째 줄에는 거리 제한을 나타내는 값 $F$가 주어집니다. ($1 \le F \le 10^{17}$)

출력

각 테스트 케이스에 대해 Case #{테스트 케이스 번호}: {문제의 정답}의 형식으로 출력합니다. 총 이동 거리가 $F$ 이하인 경로가 단 하나도 없다면 NO SOLUTION을 정답 대신 출력합니다.

문제 풀이