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

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

2828번: 사과 담기 게임

사과 담기 게임 

다국어

한국어   

시간 제한            메모리 제한                       제출                        정답                          맞힌 사람             정답 비율

1 초

128 MB

6630

3167

2667

49.471%

 

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

 

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

5 1
3
1
5
3

예제 출력 1 

6

예제 입력 2 

5 2
3
1
5
3

예제 출력 2 

4

 

흐름

 

문제에서는 칸으로 설명했는데 범위가 존재하므로 수직선(시작-끝)으로 확인해야해서 헷갈리는 문제이다.

칸을 끝점 번호라고 생각하고 풀면 된다.

 

사실 선생님 수업을 듣다가 너무 이해가 안돼서 어떤 식으로 푸는지 보고 start,end 정해서 내 식대로 풀었다.

100% 나왔으니 맞는 코드이다!

 

코드

#include <bits/stdc++.h>
using namespace std;
int m,n,j, temp,s,e, ret; //s:start, e:end
int main(){
    //1. 입력받기
    cin>>n>>m>>j;
    s=0; //기본값
    for(int i=0;i<j;i++){ //사과 떨어지는 개수만큼 반복
        cin >> temp;
        e = s+m; //s에 따라 조정
        //2. 이동거리 구하기
        if(s<temp && temp <= e) continue; //이동 X
        if(temp<=s){//사과 바구니의 왼쪽 밖에 위치
            ret += s-temp+1; //이동거리 업데이트
            s-= (s-temp+1); //위치 업데이트           
        } // 사과 바구니의 오른쪽 밖에 위치
        else{ //temp>e
            ret += (temp-e); //이동거리 업데이트
            s += (temp-e); //위치 업데이트          
        }
    }
    //3. 이동거리 출력
    cout << ret << "\n";
    return 0;
}