[백준 2828] 사과 담기 게임

https://www.acmicpc.net/problem/2828

2828번: 사과 담기 게임

 

풀이 설명

- 문제 속 바구니의 좌표는 1차원 실선 위에 나타낼 수 있으며 좌표의 최소 값은 1 최대 값은 10입니다.
- 단 최대값은 테스트 케이스마다 다를 수 있습니다.

- 사과의 위치와 상관 없이, 처음 바구니의 위치는 1에 위치 합니다.
- 사과를 담으러 가는 거리의 총합을 최소화 하려면 각 경우의 수에서 사과를 담으러 가는 거리를 최소화해야 합니다.
- 이 때 거리를 최소화하려면 바구니의 범위를 통해  최소 이동 거리를 계산해야 합니다.
- 이러한 이동거리를 계산하기 위해서는 기준점이 필요한데, 
- 문제에서 초기 위치가 제일 왼쪽에 있었으므로 왼쪽 끝 좌표를 기준으로 삼았습니다.
- 그림으로 표현하면 아래와 같습니다.

- 기준점을 왼쪽 끝으로 잡았으므로 왼쪽끝 좌표를 "기준점"으로 가정하고 사과를 담으러 움직일지 결정합니다.

- 1. 사과의 낙하 위치가 기준점과 정확히 같다면 움직이지 않습니다.
-  2. 사과의 낙하 위치가 기준점보다 크다면(오른쪽이라면), 
-  2.1. 바구니의 크기(범위)가 낙하 위치를 포함할 수 있다면 움직이지 않습니다.

   -> 바구니의 오른쪽 끝 좌표가 사과의 낙하 위치보다 크거나 같다면
- 2.2. 그렇지 않을 경우에는 오른쪽 끝 좌표가 사과의 낙하 좌표가 될 때까지 움직입니다.
-  3. 사과의 낙하 위치가 기준점보다 작다면(왼쪽이라면), 사과의 낙하 위치까지 이동해야 합니다.

        (바구니를 돌리거나 할 수 없으므로)

- 위의 조건에서 1번과 2.1.번의 조건을 제외하고는 바구니의 이동거리를 계산해야 합니다.
- 이 때, 바구니가 이동한 거리를  distance, 사과의 낙하 위치를 x,

- 사과 바구니의 왼쪽 끝 좌표를 left, 바구니의 크기를 M이라고 할 때
- 바구니의 오른쪽 끝 좌표의 값은 left + M -1 로 구할 수 있습니다.

- 이 때 일차식의 두 항 (M-1) 을 특별히 gap으로 정의하기로 했습니다.

-  바구니가 오른쪽으로 이동할 때 이동거리는 distance = x - (left + gap) 으로 계산할 수 있고,
-  이 때의 움직인 바구니의 기준점은 left + distance 로 구할 수 있습니다.
- 바구니가 왼쪽으로 이동할 때 이동거리는 distance = left - x 로 계산할 수 있고,
- 이때의 움직인 바구니의 기준점은 x가 됩니다.

-  따라서, 위의 계산을 통해 구해진 변수 distance의 합을 구하면,
-  총 이동 거리의 합을 구할 수 있는데, 이 값이 총 이동거리의 최소가 됩니다.

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int J = Integer.parseInt(br.readLine());
		int left = 1; // 기준점이 될 왼쪽 끝 좌표 값
		int ans = 0; // 총 이동거리의 합
		int gap = M-1; // 바구니의 오른쪽 끝 좌표를 구하기 위한 FACTOR
		
		for(int j = 0 ; j < J ; j ++) {
			int x = Integer.parseInt(br.readLine());
			int distance = 0;	// 사과가 좌표 x에 떨어질 경우 이동해야하는 거리
			if(left == x) continue;			
			else if( left < x ) { 			
				if(left+gap >= x) continue;
				distance = x - (left+gap); 
				ans += distance;
				left += distance;
				
			}else if (left > x) {			
				distance = left - x;
				ans += distance;
				left = x;				
                
			}
		}		
		System.out.println(ans);		
	}
}