[2828번] 사과 담기 게임

문제 기출 : [https://www.acmicpc.net/problem/2828]

 

 

풀이 방법

[그리디알고리즘] 접근   배열과 인덱스 개념만 알면 충분히 풀 수 있는 문제.   바구니 이동 index 계산 법   이 문제에서 중요한건 M은 N보다 항상 작으므로 신경쓰지 않아도 된다. 다음 식을 적용한다. 1. 사과의 위치가 바구니 위치 범위에 포함되면 움직이지 않는다. 2. 사과의 위치가 바구니 끝 위치보다 크면 바구니 첫 위치와 끝 위치에(사과 index - 바구니 끝 index)를 더해준다. 3. 사과의 위치가 바구니 끝 위치보다 크면 바구니 첫 위치와 끝 위치에(사과 index - 바구니 첫 index)를 더해준다. 4. 사과의 위치가 바구니 위치 범위에 포함되지 않으면 더해준 값을 누적한다.   최종적으로 누적된 index가 바로 움직인 최소 값이 될 수 있다.

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;

		try {
			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[] location = new int[j];

			for (int i = 0; i < j; i++) {
				location[i] = Integer.parseInt(br.readLine()) - 1;
			}

			int baskitStartIndex = 0;
			int baskitEndIndex = m - 1;
			int plusIndex = 0;

			for (int i = 0; i < j; i++) {
				if(location[i] >= baskitStartIndex && location[i] <= baskitEndIndex) {
					continue;
				}
				
				if (location[i] < baskitStartIndex) {
					plusIndex = location[i] - baskitStartIndex;
				} else if (location[i] > baskitEndIndex) {
					plusIndex = location[i] - baskitEndIndex;
				}
				
				baskitStartIndex += plusIndex;
				baskitEndIndex += plusIndex;
				answer += Math.abs(plusIndex);
				
			}

			System.out.println(answer);

		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}