[BOJ]10655번: 마라톤 1

www.acmicpc.net/problem/10655

---

수학 문제입니다.

 

1번부터 N번 체크포인트까지 순서대로 이동한다는 제약이 있습니다.

그러므로 정답 후보들끼리도 하나의 체크포인트를 제외하여도 나머지 경로는 동일합니다.

 

예시)

 

1-2-3-4-5 경로가 있다고 가정

 

1. 2번 체크포인트 제외하는 경우

1-3-4-5

 

2. 3번 체크포인트 제외하는 경우

1-2-4-5

 

3. 4번 체크포인트 제외하는 경우

1-2-3-5

 

즉, x번 체크포인트를 제외한다고 가정하면

 

x-1번 체크포인트 -> x번 체크포인트

x번 체크포인트 -> x+1번 체크포인트

 

위 두 경로만 빼면 나머지 경로는 다른 정답후보들과 동일하다는 뜻입니다.

 

풀이)

 

1. 1번부터 N번 체크포인트까지의 경로를 전부 구합니다.

2. 2번~N-1번 체크포인트에 대해 아래 값을 구해봅니다.

 

i를 임의의 i번째 체크포인트라 가정하고 아래 값을 구해봅니다.

//checkpoint[x] - checkpoint[x-1]은 x번째 체크포인트와 x-1번째 체크포인트 사이의 거리

int before_distance = (checkpoint[i] - checkpoint[i-1]) + (checkpoint[i+1] - checkpoint[i]);
int new_distance = (checkpoint[i+1] - checkpoint[i-1]);
int diff = before_distance - new_distance;

 

2번~N-1번 체크포인트에 대해 위 값을 구했을 때

diff값이 가장 큰 체크포인트가 제외하였을 때 최단 경로가 되는 체크포인트입니다.

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ10655.cc