백준 2828 사과담기 게임 c++

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

그리디 알고리즘, 구현

제출 일자

2025년 2월 20일 21:25:46

문제 설명

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M

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

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

입력

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

출력

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

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;
int N, M, J;

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

	cin >> N>> M>>J;

	int left = 1;
	int right = left + M - 1;
	int iCount = 0;
	vector<int> vApplePosition;
	vApplePosition.resize(J);
	for (int i = 0; i < J; ++i)
	{
		cin >> vApplePosition[i];
	}

	for (int i = 0; i < J; ++i)
	{
		if (vApplePosition[i] >= left && vApplePosition[i] <= right)
			continue;
		
		for (int j = 0; j < N; ++j)
		{
			if (vApplePosition[i] < left)
			{
				iCount++;
				left--;
				right--;
			}
			else if (vApplePosition[i] > right)
			{
				iCount++;
				left++;
				right++;
			}
			else
				break;
		}

	}

	cout << iCount << endl;


	return 0;
}

 

바구니를 왼쪽과 오른쪽 범위를 두어서 해결하였다.