[Baekjoon(백준)][2828번] 사과 담기 게임(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "사과 담기 게임" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 조작하는 바구니를 이용해 떨어지는 사과를 모두 잡는 게임입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

2828번: 사과 담기 게임

문제 개요

"사과 담기 게임"은 상근이가 조작하는 바구니를 이용해 떨어지는 사과를 모두 잡는 게임입니다. 게임의 목표는 사과를 모두 잡기 위해 바구니가 이동해야 하는 거리의 최솟값을 찾는 것입니다.

해결 방법

게임은 N칸으로 나뉘어진 스크린에서 진행되며, 바구니는 M칸을 차지합니다. 사과는 하나씩 떨어지며, 바구니는 이 사과가 떨어지는 칸을 커버해야 합니다. 사과가 떨어지는 위치가 바구니의 범위 내에 없을 경우, 바구니를 움직여야 합니다. 이때, 최소 이동 거리를 구하기 위해 각 사과가 떨어지는 위치와 바구니의 현재 위치를 비교하여 필요한 최소 이동 거리를 계산합니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

int n, m, j; // 스크린의 크기, 바구니의 크기, 사과의 수
vector<int> table; // 사과가 떨어지는 위치들

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

    cin >> n >> m >> j; // 입력 받기

    for (int i = 0; i < j; i++) {
        int temp;
        cin >> temp;
        table.push_back(temp); // 사과의 위치 저장
    }

    int start = 1; // 바구니 시작 위치
    int sum = 0; // 총 이동 거리

    for (int i = 0; i < table.size(); i++) {
        int end = start + m - 1; // 바구니 끝 위치
        if (table[i] >= start && table[i] <= end) continue; // 사과가 바구니 범위 내에 있는 경우

        // 사과가 바구니 범위 밖에 있는 경우
        if (table[i] < start) {
            sum += (start - table[i]); // 왼쪽으로 이동
            start = table[i];
        } else {
            start += (table[i] - end); // 오른쪽으로 이동
            sum += (table[i] - end);
        }
    }
    cout << sum << "\n"; // 결과 출력
}

코드 설명

이 코드는 사과가 떨어지는 위치에 따라 바구니가 필요한 최소 이동 거리를 계산합니다. 사과가 바구니 범위 내에 떨어지는 경우 이동할 필요가 없고, 그렇지 않은 경우 바구니를 사과가 있는 위치까지 이동시켜야 합니다. 이 과정에서 발생하는 총 이동 거리를 합산하여 출력합니다.

결론

"사과 담기 게임" 문제는 바구니의 이동 범위를 계산하고, 사과의 위치에 따라 최소한의 이동으로 모든 사과를 잡는 전략을 세우는 데 초점을 맞춥니다. 각 단계에서의 최적의 이동을 결정하는 것이 중요합니다.