[PS] 백준 2828 사과 담기 게임

이번에는 백준 2828번 사과 담기 게임 문제를 풀어보았습니다.

이 문제는 바구니가 차지하는 구간을 기준으로, 떨어지는 사과를 모두 담기 위해 바구니를 얼마나 움직여야 하는지를 구하는 문제입니다.

핵심은 매번 바구니 전체를 다시 생각하기보다, 현재 바구니가 커버하는 범위가 어디인지를 기준으로 판단하는 것이었습니다.

---

문제 설명

스크린은 N칸으로 이루어져 있고, 바구니는 연속된 M칸을 차지합니다.

처음에는 바구니가 맨 왼쪽 M칸을 차지하고 있습니다.

그 뒤 사과가 순서대로 하나씩 떨어지는데,

사과가 떨어지는 위치가 현재 바구니가 차지하는 범위 안에 있으면 그대로 담을 수 있고,

범위를 벗어나면 바구니를 왼쪽이나 오른쪽으로 움직여야 합니다.

이때 모든 사과를 담기 위해 움직인 거리의 합의 최솟값을 구하면 됩니다.

---

풀이 아이디어

이 문제는 바구니의 왼쪽 끝 위치를 기준으로 생각하면 편했습니다.

예를 들어 현재 바구니의 왼쪽 끝이 cur_pos라면,

바구니가 커버하는 범위는

cur_pos ~ cur_pos + M - 1

입니다.

따라서 사과가 떨어지는 위치 position이

• 이 범위 안에 있으면 이동할 필요가 없고
• 범위보다 왼쪽이면 왼쪽으로 이동
• 범위보다 오른쪽이면 오른쪽으로 이동

하면 됩니다.

즉, 매번 현재 바구니 범위 안에 사과가 들어오는지 확인하고,

벗어나는 경우에만 필요한 만큼만 이동 거리를 더하는 방식으로 해결할 수 있습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    int j;
    cin >> j;
    int cur_pos = 1;
    int dist_cnt = 0;
    for (int i = 1; i <= j; i++) {
        int position;
        cin >> position;
        if (position >= cur_pos && position <= cur_pos + M - 1)
            continue;

        if (position < cur_pos) {
            dist_cnt += (cur_pos - position);
            cur_pos = position;
        } else {
            dist_cnt += (position - cur_pos - M + 1);
            cur_pos = (position - M + 1);
        }
    }

    cout << dist_cnt << endl;
}

---

풀이 흐름

1. N, M을 입력받는다.
2. 사과 개수 j를 입력받는다.
3. 처음 바구니의 왼쪽 끝 위치를 1로 둔다.
4. 각 사과가 떨어지는 위치를 하나씩 입력받는다.
5. 현재 바구니 범위 안에 있으면 그대로 넘어간다.
6. 범위보다 왼쪽이면 왼쪽으로 이동한 거리만큼 더한다.
7. 범위보다 오른쪽이면 오른쪽으로 이동한 거리만큼 더한다.
8. 모든 사과를 처리한 뒤 총 이동 거리를 출력한다.

---

구현 포인트

1. 바구니의 크기는 M, 커버 범위는 cur_pos ~ cur_pos + M - 1

이 문제에서 가장 중요한 기준은 바구니의 현재 범위입니다.

코드에서는 바구니의 왼쪽 끝을 cur_pos로 두고,

현재 바구니가 차지하는 범위를 다음처럼 판단했습니다.

position >= cur_pos && position <= cur_pos + M - 1

즉, 바구니 크기가 M이므로
현재 커버 가능한 칸은 cur_pos부터 cur_pos + M - 1까지입니다.

이 범위를 기준으로 사과가 안에 있는지, 밖에 있는지를 판단했습니다.

---

2. 범위 안에 있으면 이동할 필요 없음

사과가 현재 바구니 범위 안에 있다면 이미 담을 수 있으므로 이동하지 않습니다.

if (position >= cur_pos && position <= cur_pos + M - 1)
    continue;

이 경우에는 이동 거리도 증가하지 않고, 바구니 위치도 그대로 유지됩니다.

---

3. 왼쪽으로 벗어나면 그만큼 왼쪽으로 이동

사과가 바구니 범위보다 왼쪽에 있다면,

현재 바구니의 왼쪽 끝을 그 사과 위치까지 옮기면 됩니다.

if (position < cur_pos) {
    dist_cnt += (cur_pos - position);
    cur_pos = position;
}

즉, 이동 거리는 cur_pos - position이고,
이후 바구니의 새 왼쪽 끝은 position이 됩니다.

---

4. 오른쪽으로 벗어나면 오른쪽 끝이 사과를 포함하도록 이동

사과가 범위보다 오른쪽에 있다면,

바구니의 오른쪽 끝이 그 사과 위치를 포함할 수 있도록 옮겨야 합니다.

dist_cnt += (position - cur_pos - M + 1);
cur_pos = (position - M + 1);

이 부분은 현재 바구니 범위가 cur_pos ~ cur_pos + M - 1라는 점을 이용한 계산입니다.

사과가 position에 있을 때,

바구니가 그 사과를 포함하려면 왼쪽 끝은 position - M + 1이 되어야 합니다.

---