백준] 2828 - 사과 담기 게임(COCI 2011/2012)

시간 제한 : 1초

메모리 제한 : 128MB

입력

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

출력

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

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int n, m, j, apple, mov = 0, start, end;
	cin >> n >> m >> j;
	start = 1, end = m;
	for (int i = 0; i < j; i++)
	{
		cin >> apple;
		if (start <= apple && end >= apple)
			continue;
		if (start > apple)
		{
			mov += start - apple;
			end -= start - apple;
			start = apple;
		}
		else
		{
			mov += apple - end;
			start += apple - end;
			end = apple;
		}
	}
	cout << mov;
}

Tip

그리디로 접근하여 푸는 문제이며, 매 순간 가장 짧게 이동하는 경로만을 찾아나가면 된다.