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

 

2828번: 사과 담기 게임

 

 

문제

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

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

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

 

 

 

 

입력

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

 

 

 

출력

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

 

 

 

풀이과정

문제의 설명은 위와 같다.

• n은 스크린의 크기. 
• m은 바구니의 길이 ( 시작지점은 1 )
• j는 떨어지는 사과의 개수 ( 들어오는 순서대로 떨어진다. )

 

위에 예제의 풀이를 적어보면

1번째로 떨어지는 사과는 1번에 떨어지기때문에 움직이지않아도 되고

2번째로 떨어지는 사과는 5번에 떨어지기때문에 4번까지 이동을 해야 사과를 받을 수 있다.

( m이 2이기때문에 4번까지만 이동해도 5번까지 범위안에 들어온다. )

3번째로 떨어지는 사과는 3번에 떨어지기때문에 기존 4번위치에 있는 바구니를 3번으로 이동해줘야한다.

그래서 2번에서 3 움직이고 3번에서 1 움직여서 3 + 1 로 예제출력값이 4가 되는 형식이다.

 

그래서 해당로직은 2번쨰 같이 증가을해서 앞으로 가는 경우와 3번째와 같이 감소를 해서 뒤로가는 경우 총 2가지가 있어

현재위치 + 바구니의 길이보다 사과가 떨어진 위치가 더 멀리있다면 앞으로 이동을 해야하는 것이고,
( 현재위치 + 바구니의 길이 < 사과가 떨어진위치 )

현재위치 + 바구니의 길이보다 사과가 떨어진 위치가 더 뒤에 있다면 뒤로 이동을 하는 로직으로 구성을 하였다.

( 현재위치 + 바구니의 길이 > 사과가 떨어진위치 )

 

 

code

#include <iostream>

int		main(void)
{
	int n, m, j, temp, end;
	int count = 0, place = 1;

	std::cin >> n >> m >> j;
	for (int i = 0; i < j; i++) {
		std::cin >> temp;
		if (place + m - 1 < temp) {
			end = temp - (place + m - 1);
			count += end;
			place = (place + end);
		}
		else if (place > temp) {
			count += place - temp;
			place = temp;
		}
	}
	std::cout << count;

	return (0);
}

 

후기

머리속으로 정리자체가 쉽게되지않아 꽤나 풀이에 시간이 오래걸린 거 같다.