2828번: 사과 담기 게임

문제

N칸으로 나누어진 스크린 아래에 M칸을 차지하는 바구니가 있습니다. 처음에 바구니는 왼쪽 끝(1번 칸부터 M번 칸)에 위치해 있습니다. 위에서 사과가 하나씩 떨어지며, 바구니를 좌우로 움직여 모든 사과를 받아야 합니다. 사과가 떨어지는 위치가 순서대로 주어질 때, 모든 사과를 담기 위해 바구니가 이동해야 하는 최소 거리를 구하는 문제입니다.

• 입력:
  • 첫째 줄: 스크린의 크기 N과 바구니의 크기 M
  • 둘째 줄: 떨어지는 사과의 개수 J
  • 셋째 줄부터 J개의 줄: 사과가 떨어지는 위치
• 출력: 바구니의 최소 이동 거리

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

풀이

바구니가 사과를 받기 위해 필요한 만큼만 최소한으로 이동해야 하는 그리디(Greedy) 문제입니다. 바구니의 왼쪽 끝과 오른쪽 끝 좌표를 기록해두고, 사과가 떨어지는 위치와 비교하여 바구니를 이동시킵니다.

1. 바구니 초기화: 바구니의 시작 위치(s)는 1, 끝 위치(e)는 M으로 초기화합니다.
2. 사과 위치 비교 및 이동 (그리디 연산): 떨어지는 사과의 위치를 x라고 할 때 세 가지 경우가 발생합니다.
   • 사과가 바구니 범위 안에 떨어질 때 (s <= x && x <= e): 바구니를 움직일 필요가 없으므로 아무 작업도 하지 않습니다.
   • 사과가 바구니보다 왼쪽에 떨어질 때 (s > x): 바구니를 왼쪽으로 이동시켜야 합니다. 이동 거리는 s - x가 되며, 이를 정답(ans)에 누적합니다. 이동 후 바구니의 새 위치는 시작점이 x, 끝점이 x + M - 1이 됩니다.
   • 사과가 바구니보다 오른쪽에 떨어질 때 (e < x): 바구니를 오른쪽으로 이동시켜야 합니다. 이동 거리는 x - e가 되며, 이를 정답에 누적합니다. 이동 후 바구니의 새 위치는 끝점이 x, 시작점이 x - M + 1이 됩니다.
3. 모든 사과에 대해 위 과정을 반복한 뒤 누적된 이동 거리(ans)를 출력합니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       int n = Integer.parseInt(st.nextToken()); // 스크린 크기
       int m = Integer.parseInt(st.nextToken()); // 바구니 크기
       int j = Integer.parseInt(br.readLine());  // 사과 개수

       // 바구니의 왼쪽 끝(s)과 오른쪽 끝(e) 초기화
       int s = 1;
       int e = m;

       int ans = 0; // 총 이동 거리
       
       while (j-- > 0) {
          int x = Integer.parseInt(br.readLine()); // 사과가 떨어지는 위치
          
          // 1. 사과가 바구니의 왼쪽에 떨어지는 경우
          if (s > x) {
             ans += s - x; // 이동 거리 누적
             s = x;        // 바구니의 왼쪽 끝을 사과 위치로 맞춤
             e = x + m - 1; // 바구니의 오른쪽 끝 갱신
          } 
          // 2. 사과가 바구니의 오른쪽에 떨어지는 경우
          else if (e < x) {
             ans += x - e; // 이동 거리 누적
             e = x;        // 바구니의 오른쪽 끝을 사과 위치로 맞춤
             s = x - m + 1; // 바구니의 왼쪽 끝 갱신
          }
          // 3. 사과가 바구니 안에 떨어지는 경우는 이동할 필요 없으므로 생략
       }

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

그리디 알고리즘 (Greedy), 구현 (Implementation)