[백준 2828] 사과 담기 게임

문제

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

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

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

입력

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

출력

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

 

설계

1. n,m,j,result를 입력값을 받는다.

   1-1. 가장 왼쪽의 값을 최초 1로 지정한다.

2. J만큼 반복문을 돌린다.

3.  반복 마다 사과의 위치(Position)를 받는다. 

4. 바구니의 왼쪽 끝을 기준으로 오른쪽 끝 바구니 위치를 구한다.

5. 입력 받은 사과 낙하의 위치가 바구니의 왼쪽 오른쪽 사이라면 아무 영향도 주지 않는다.

6. 입력 받은 사과 낙하 위치가 바구니를 벗어나는 상황을 두가지 경우로 나눈다.

7. 바구니의 왼쪽으로 떨어지는가, 오른쪽으로 떨어지는가

8. 왼쪽으로 떨어질 경우 현재 왼쪽 바구니의 위치에서 Position을 뺀뒤 이동 거리를 구한다.

9. 오른쪽을 떨어질 경우 Position에서 바구니의 오른쪽 위치를 빼서 이동 거리를 파악한다. 그리고 기존 왼쪽 바구니의 위치에 뺀거리를 더한다. 

10. 결과 값을 반환한다.

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int n,m,j,position,rightend,leftend, result = 0;
int main() {
    cin >> n >> m >> j; // 스크린 크기, 바구니 크기 , 사과 떨어지는 횟수

    leftend = 1;
    // j번 만큼 입력값을 받는다. 
    for ( int i = 0 ; i < j; i++ ) {
        cin >> position;
        rightend = leftend + m - 1;

        // -1의 이유는 1부터 시작이아니라 바구니의 크기는 왼쪽 끝을 포함하기 때문이다. 왼쪽 끝 바구니의 위치가 1이다. 바구니의 크기는 3이다. 
        // 여기서 바구니의 위치 1에 바구니의 크기 3을 더하면 바구니의 오른쪽 끝 위치가 4가 된다. 
        // 하지만 아래 그림을 보면 오른쪽 끝 바구니의 위치는 3이다. 
        // 1 2 3 4 5   => 스크린
        // 1 2 3       => 바구니

        if ( position >= leftend && position <= rightend ) {

            continue;

        }

        if ( position < leftend) {

            result += (leftend - position);
            leftend = position;

        }

        if ( position > rightend) {

            result += (position - rightend);
            leftend += (position - rightend);

        }

    }
    cout << result;
}

어려웠던 점

바구니의 위치를 결정하는 것 다들 왼쪽 끝과 오른쪽 끝을 이야기해서 살짝 했갈렸다. 나만의 방식으로 이해하기로는 바구니의 왼쪽 위치를 기준으로 바구니의 크기를 더하게 되면 바구니의 크기보다 1이 큰 값이 나오게된다. 이유는 왼쪽을 기준으로 가장 첫번째 바구니에 바구니의 크기를 더하기 때문이다. 

 

예를 들어 바구니가 들어갈 수 있는 9개의 칸을 가진 라인이 있다고 가정해보자.

1 2 3 4 5 6 7 8 9 

1 2 3

3개의 바구니를 이어붙여서 길이가 3인 바구니를 오른쪽 왼쪽으로 옮겨 다닐 수 있다. 오른쪽으로 3칸을 이동한다고 하면 1(현재위치 ) + 3(이동) 이동 후 맨 왼쪽 바구니의 위치는 4가된다. 여기서 오른쪽 바구니의 위치를 구하려면? 4에다 3을 더하면 된다. 그럼 7이된다. 아래그림을 봐보자.

 

1 2 3 4 5 6 7 8 9 

           1 2 3 

 

뭔가 이상하지 않은가? 6이 되어야 정상이다. 이유는 바구니의 크기는 맨 왼쪽 바구니를 포함하고 있기 때문이다. 따라서 바구니의 크기를 통해 왼쪽 바구니의 위치를 기준으로 맨 오른쪽 바구니의 위치를 구하려면 자신의 길이 1을 빼주는 작업이 필요하다.