[백준2828]사과담기게임_C++

그리디  알고리즘

문제

 

문제, 입출력

그리디 알고리즘

입출력 예제

 

★문제설명 :

N칸의 스크린이 있고, 그 아래에 M칸을 차지하는 바구니가 있음.

이때 사과의 개수 j개가 떨어지는데, 이를 바구니를 이동시켜 받아야된다. 이때 바구니의 최소 이동거리를 구하는 문제.

 

★풀이 : 

스크린을 이동하는 바구니의 크기가 입력값에 달라지고, 바구니 이동시 바구니의 위치를 구현해야 함. 

    -->구현: 바구니의 앞쪽 인덱스와 뒤쪽 인덱스를 달리함. 앞쪽은 front, 뒤쪽은 back 변수를 이용

                (이때, if문으로 조건 검색할 때 등호랑 부등호 방향이랑 인덱스 잘 생각해서 쓰기)

사과가 바구니 안에 들어갈 때 까지 이동시켜야 된다.

    -->구현: while(1)을 돌려, 바구니에 사과가 들어갈 때까지 반복시킨다.  

 

#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

int main() {
	int n, m, num;
	int dap = 0; //답 : 이동거리
	int front = 0;
	int back;

	cin >> n >> m;
	back = m;

	int apple;
	cin >>num;
	for (int i = 0; i < num; i++) {
		cin >> apple;
		while (1) {  //사과 담을 때까지 이동
				if (front < apple && apple <= back)  //사과 담으면 탈출~
					break;

				if (apple <= front)	//상자보다 앞쪽인 경우
				{
					front--;
					back--;
					dap++;
				}

				if (apple > back) { //상자보다 뒤쪽인 경우
					front++;
					back++;
					dap++;
				}
			}
	}
	cout << dap;
}