[C++] 백준 2828번: 사과 담기 게임

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

2828번: 사과 담기 게임

1. 문제

 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.
 스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.
 바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

2. 입력

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

3. 출력

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

4. C++ 코드

#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int screen, basket, apple;
	cin >> screen >> basket;
	cin >> apple;
	int* arr = new int[apple];
	int location;
	for (int i = 0; i < apple; ++i) {
		cin >> location;
		arr[i] = location;
	}
	int left = 0, right = basket - 1;
	int cost = 0;
	for (int i = 0; i < apple; ++i) {
		int dropIdx = arr[i] - 1;
		int distance = 0;
		if (dropIdx < left) {
			distance = left - dropIdx;
			cost += distance;
			left -= distance;
			right -= distance;
		}
		else if (dropIdx > right) {
			distance = dropIdx - right;
			cost += distance;
			left += distance;
			right += distance;
		}
	}
	cout << cost;
	delete[] arr;

	return 0;
}

5. 문제 풀이

  바구니의 사이즈를 고려하여 최소한의 이동으로 사과가 떨어지는 위치에 바구니를 이동시키도록 하는 문제이다. screen, basket, apple은 각각 스크린의 사이즈, 바구니의 크기, 떨어지는 사과의 개수를 담는 변수이다. apple이 저장한 값만큼 사과가 떨어지므로 각각 사과가 떨어지는 위치를 저장하는 포인터 배열 arr를 선언하였다.
 바구니를 최소한으로 이동시키려면 사과가 떨어지는 위치가 주어졌을 때, 바구니를 왼쪽으로 옮겨야하는지 오른쪽으로 옮겨야하는지, 그리고 움직이지 않아도 되는지를 알아야한다. 이를 고려하여 바구니의 크기가 주어졌을 때 왼쪽과 오른쪽의 인덱스를 가리키는 left, right 변수를 선언하였고, 최소 이동거리인 cost를 0으로 초기화하였다.
 떨어지는 사과의 개수만큼 반복문을 수행하면서 arr에는 사과가 떨어지는 위치가 담겨있으므로 인덱스를 저장하기 위하여 dropIdx에 값을 할당하였다. dropIdx와 left, right의 값을 비교한 후,  바구니를 이동시켜야 하는 경우 distance 에 바구니의 이동할 거리를 저장하여 cost에 더해준다. 반복문이 끝난 후 결과 값을 출력한다.