개구리 주호는 $x$축 위에 사는 $N$마리의 개구리 중 하나를 선택하여 만나려고 한다. $i$번째 개구리를 선택해 만나려 했을 때, 개구리 주호는 $x=S$에서, $i$번째 개구리는 $x=E_i$에서 동시에 출발하여 움직인다.

이때, 두 개구리는 각각 다음과 같이 움직인다. 실제로 좌표가 변하지 않더라도 아래 과정을 따라야 함에 유의하라.

상대 개구리를 바라보는 방향으로 움직이며, 반대 방향으로는 움직이지 않는다.
상대 개구리를 뛰어넘지 않는다.
상대 개구리를 향해 움직일 때 맨 처음에 반드시 점프를 한 번 해야 한다.
점프를 한 번 한 뒤에는 걸어서 움직여야 한다.
점프하거나 걸을 때는 반드시 정수 거리만큼 움직여야 한다.
이 개구리들은 신기한 특징이 있는데, 최대 거리 $K$만큼 점프할 수 있으며, 정확히 거리 $K$만큼 점프하기 적합하게 진화했다는 점이다. 그래서 거리 $d$ $(0 \leq d \leq K)$만큼 점프하면 체력이 $K-d$만큼 소모된다. 즉, $d = 0$이면 제자리로 점프하면서 $K$만큼의 체력이 들고, $d = K$이면 $K$만큼 점프하고 $0$만큼의 체력이 소모된다.

한 번 점프한 뒤에는 상대방 개구리를 만날 때까지 걷는다. 이때 $1$씩 걸을 때마다 체력 $L$이 소모된다.

개구리들에게 체력은 생존을 위해 매우 중요하다. 그들은 서로를 향해 움직일 때 서로의 체력 소모의 합이 최소가 되도록 움직인다. 개구리 주호는 $N$마리의 개구리 중 자신과 만나기 위해 소모되는 체력의 합이 가장 작은 개구리 하나를 선택하여 만나려고 한다. 주호를 위해 서로의 체력 소모량의 합의 최솟값과 주호가 만날 개구리의 번호를 찾아주자.

입력

첫째 줄에 $S$와 $N$이 공백으로 구분되어 주어진다.

둘째 줄에 개구리의 위치를 뜻하는 $E_1, E_2, \cdots, E_N$이 공백으로 구분되어 주어진다. 주호를 포함한 모든 개구리의 좌표는 서로 다르다.

셋째 줄에 $K$와 $L$이 공백으로 구분되어 주어진다.

출력

서로의 체력 소모의 합의 최소와 그 개구리의 번호를 공백으로 구분하여 출력하라.

만약 체력 소모의 합이 최소가 되도록 만날 수 있는 개구리가 여러 마리일 경우 그중 아무거나 하나를 출력한다.

제한
$0 \leq S \leq 100\,000$ 
$1 \leq N \leq 10\,000$ 
$0 \leq E_{i} \leq 100\,000$ $(1 \le i \le N)$ 
$1 \leq K \leq 100\,000$ 
$1 \leq L \leq 10\,000$ 
$E_i \neq S$ $(1 \le i \le N)$ 
$E_i \neq E_j$ $(1 \le i < j \le N)$ 

어떻게 풀어야할까?

문제가 길어서 읽고 이해하는데 시간이 좀 걸렸다.
그래도 핵심만 얘기하자면
s: 주호 개구리 위치, n: 개구리 수
E[1], E[2], ..., E[n]: 개구리 위치
k: 개구리 최대 점프 거리, l: 1걸을 때마다 소모되는 체력
이런 입력이 주어지고 체력 소모가 최소인 경우를 찾는 것이다.

풀이 아이디어

주호 개구리를 제외한 개구리들의 위치를 arr[i]에 담고
각 개구리와 주호 개구리 사이의 거리를 distance라고 할 때
distance > 2k
distance <= 2k
2가지 경우를 나눠서 체력을 계산하고
특히 distance <= 2*k일 때 거리가 홀수인 경우와 짝수인 경우를 나눠서 계산했다.
홀수인 경우 좌우 개구리의 뛰는 거리가 다르기 때문이다.
예를 들어 거리가 5고 최대 점프 거리가 3이면 한쪽은 3을 뛰고 다른 쪽은 2를 뛰어서
좌우 개구리의 체력소모가 다르다.

풀이 코드

import java.util.*;
import java.io.*;

public class _30012 {
   public static void main(String[] args) throws IOException{
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st = new StringTokenizer(br.readLine(), " ");
       
       // s: 주호 개구리 위치, n: 개구리 수
       int s = Integer.parseInt(st.nextToken());
       int n = Integer.parseInt(st.nextToken());

       // arr: 개구리 위치
       int[] arr = new int[n];
       st = new StringTokenizer(br.readLine(), " ");
       for(int i=0; i<n; i++){
           arr[i] = Integer.parseInt(st.nextToken());
       }

       // k: 개구리 최대 점프 거리, l: 1걸을 때마다 소모되는 체력
       st = new StringTokenizer(br.readLine(), " ");
       int k = Integer.parseInt(st.nextToken());
       int l = Integer.parseInt(st.nextToken());

       // dp: i번째 개구리까지의 체력 소모량
       int[] dp = new int[n+1];

       // 각 개구리 위치 계산 
       for(int i=0; i<n; i++){
           int distance = Math.abs(arr[i] - s);
           int cost = 0;

           // 점프로 닿지 않는 거리일 때
           if(distance > 2*k){
               cost += (distance-2*k)*l;
           }
           // 점프로 닿는 거리일 때            
           else if(distance <= 2*k){
               if (distance % 2 == 0) {
                   cost += (k-distance/2)*2;
               } 
               else if (distance % 2 == 1) {
                   cost += (k-distance/2)*2 - 1;
               }
           }
           dp[i] = cost;
       }

       // 최소 체력 소모량과 인덱스 찾기       
       int min = Integer.MAX_VALUE;
       int idx = 0;
       for(int i=0; i<n; i++){
           if(min > dp[i]){
               min = dp[i];
               idx = i+1;
           }
       }

       // 출력: 서로의 체력 소모 합의 최소, 그 개구리 번호
       System.out.println(min+" "+idx);
   }
}

후기

난이도는 생각보다 높지 않은 실버3 문제였음에도 꽤 어렵게 느껴졌다.
우선 문제 제시문이 길어 조건과 입력값 종류가 많았기 때문이다.
그리고 최소 체력 소모량을 계산하는 점화식을 찾아야했는데
처음에는 어떻게 하지 고민하다가 모든 경우를 잘게 나눠서 생각하다보니
수월하게 찾을 수 있었다.