[백준] 2828 사과 담기 게임(JAVA)

2828번: 사과 담기 게임

문제

---

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

N : 스크린 칸 M : 바구니가 위치한 칸 (시작 칸) J : 사과의 갯수

 

출력

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

 

예제 입력

5 1
3
1
5
3

예제 출력

6

 

 

요구 사항 분석

---

이 문제를 해결하려면 사과가 떨어지는 것을 시뮬레이션하고 그에 따라 바구니를 움직여 사과를 받아야 합니다.

바구니의 현재 위치를 추적하고 각 사과를 잡기 위해 이동해야 하는 거리를 계산할 수 있습니다. 그런 다음 이 거리를 합산하여 모든 사과를 잡기 위해 바구니가 이동해야 하는 총 거리를 얻을 수 있습니다.

 

접근 방법

1. N, M, J의 입력값을 읽는다.
2. 바구니의 현재 위치를 M으로 초기화한다.
3. 각 사과의 위치를 읽고 땅에 떨어지기 전에 떨어지는 거리를 계산한다.
4. 바구니가 떨어지는 사과의 경로에 있는 경우 바구니가 사과를 잡기 위해 이동해야 하는 거리를 계산한다.
5. 바구니의 현재 위치를 사과가 땅에 닿는 위치로 업데이트 한다.
6. 모든 사과가 잡힐 때까지 3-5단계를 반복한다.
7. 모든 사과를 잡기 위해 바구니가 이동한 총 거리를 출력한다.

배열에 사과 위치를 저장하여 문제에 접근 바구니의 가능한 각 시작 위치를 반복하고, 각 시작 위치에 대해 모든 사과를 잡는 데 필요한 최소 거리를 계산한다.

 

풀이

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

public class boj2828 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄에서 N과 M을 입력받음
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 두 번째 줄에서 J를 입력받음
        int J = Integer.parseInt(br.readLine());

        int left = 1; // 바구니의 왼쪽 끝 위치
        int right = M; // 바구니의 오른쪽 끝 위치
        int cnt = 0; // 이동 횟수

        for (int i = 0; i < J; i++) {
            int apple = Integer.parseInt(br.readLine());

            // 바구니를 왼쪽으로 이동해야 하는 경우
            if (apple < left) {
                cnt += left - apple; // 이동 거리를 더함
                left = apple; // 바구니 위치 업데이트
                right = left + M - 1; // 바구니 범위 업데이트
            }
            // 바구니를 오른쪽으로 이동해야 하는 경우
            else if (apple > right) {
                cnt += apple - right; // 이동 거리를 더함
                right = apple; // 바구니 위치 업데이트
                left = right - M + 1; // 바구니 범위 업데이트
            }
        }

        System.out.println(cnt);
    }
}