원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
거울
원제: 거울
문제
당신은 수직선 위에서 게임을 하고 있다. 당신의 캐릭터는 위치 에 있으며, 수직선 위에는 개의 거울이 배치되어 있다. 각 거울의 위치는 왼쪽부터 으로 나타낼 수 있다. 한 위치에 여러 개의 거울이 있을 수도 있다.
당신은 거울을 사용해 캐릭터의 위치를 바꿀 수 있다. 이때, 거울을 사용하면 캐릭터의 위치는 거울을 기준으로 점대칭인 지점으로 이동한다. 즉, 당신의 캐릭터가 위치 에 있을 때 위치 에 있는 거울을 사용하면 당신의 캐릭터는 위치 로 이동한다.
개의 거울은 정확히 한 번씩 사용되어야 한다. 즉, 한 거울을 사용하지 않고 무시할 수는 없으며, 한 거울을 두 번 이상 사용할 수도 없다. 각 거울을 모두 정확히 한 번씩 사용해야 하는 것을 제외하고는, 거울은 당신이 원하는 아무 순서대로 사용할 수 있다.
당신은 이 조건하에서 캐릭터의 위치의 최댓값을 계산하여 출력해야 한다.
제약 조건
- 주어지는 모든 수는 정수이다.
부분문제
- (7점) .
- (25점) 은 짝수, .
- (19점) 은 짝수, .
- (49점) 추가 제약 조건 없음.
입력 형식
첫째 줄에는 거울의 수 과 당신의 위치 가 공백으로 구분되어 주어진다.
둘째 줄에는 각 거울의 위치 이 공백으로 구분되어 주어진다.
출력 형식
개의 거울을 모두 정확히 한 번씩 사용했을 때 캐릭터의 최종 위치의 최댓값을 출력한다.
답이 커질 수 있으므로 일부 프로그래밍 언어에서는 64비트 정수 변수(long long)를 사용해야 할 수도 있음에 유의하라.
예제
예제 1
2 0 -1 2
6
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
번 거울을 먼저 이용하고, 그다음에 번 거울을 이용한다면, 위 그림처럼 캐릭터의 최종 위치는 이 된다. 반면, 번 거울을 먼저 이용하고, 그다음에 번 거울을 이용한다면, 캐릭터의 최종 위치는 이 된다. 고로, 이 예시의 정답은 이 된다.
예제 2
6 3 -4 -2 2 6 8 9
57
예제 3
9 9 0 1 3 3 4 5 8 9 10
49
예제 4
1 1000000000 -999999999
-2999999998