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

potatoj11n·2024년 1월 20일

백준

목록 보기

13/36

🌱 문제 설명

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

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

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

입력

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

출력

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

풀이

#include <iostream>
using namespace std;

int n,m,j, answer;//스크린, 바구니 범위, 사과 개수 j , 바구니가 이동하는 거리 answer
int main(){
   cin >> n >> m >> j;
   
   int left = 1,right = m;//바구니의 왼쪽 끝(left)과 오른쪽 끝(right)
   while(j--){//사과 개수를 줄여가면서
       int pos;//떨어질 사과의 위치
       cin >> pos;
       while(left > pos || right < pos){
//범위 내에서 떨어지면 바구니 위치 조정,바구니의 이동거리 누적
           if(pos > right) 
               right++, answer++, left++;
           else if(pos < left) 
               right--,answer++,left--;
       }
   }
   cout << answer << endl;   
}

❣️ 목표:

스크린 위에서 떨어지는 사과 여러개를 바구니에 담는 게임, 바구니의 최소 이동 거리를 구하는 것

🤔 생각해야 할 점:

만약 범위 안에 값이 존재한다면 다음 사과 위치로 넘어간다.
범위 안에 값이 없다면 count up 하고 해당 방향으로 한 칸 이동해서 다시 검사한다.
이동 거리의 최솟값 answer 출력

그리디 알고리즘( 탐욕적 알고리즘)

→그 순간에 가장 좋다고 생각하는 해답을 선택

n : 스크린의 범위 , m : 바구니의 범위, j : 사과의 개수, answer : 바구니의 이동거리
int left = 1,right = m : 바구니 왼쪽 끝은 left , 오른쪽 끝은 right 로 정해 변수 선언
사과의 위치를 입력받은 후 바구니의 위치를 조정하며 이동거리를 계산하는 while문

 while(j--){//사과 개수를 줄여가면서
        int pos;//떨어질 사과의 위치
        cin >> pos;
        while(left > pos || right < pos){
            if(pos > right) //사과의 위치가 바구니 오른쪽에 있을 경우
                right++, answer++, left++; 
								//바구니 오른쪽으로 이동, 이동거리 증가, 범위를 유지하기 위해 왼쪽 이동
            else if(pos < left) //사과가 바구니 왼쪽에 있으면
                right--,answer++,left--;
        }
    }
    cout << answer << endl;   
}