백준] 2891 - 카약과 강풍(COCI 2009/2010)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 2 ≤ S, R ≤ N)

둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

셋째 줄에는 카약을 하나 더 가져온 팀의 번호가 주어진다. 팀 번호는 중복되지 않는다.

출력

첫째 줄에 출발을 할 수 없는 팀의 최솟값을 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	int N, S, R, retire = 0;
	cin >> N >> S >> R;
	vector<int> team(N + 1, 1);
	vector<int> broken(S);
	vector<int> spare(R);
	for (int i = 0; i < S; i++)
	{
		cin >> broken[i];
		team[broken[i]]--;
	}
	for (int i = 0; i < R; i++)
	{
		cin >> spare[i];
		team[spare[i]]++;
	}

	for (int i = 1; i <= N; i++)
	{
		if (team[i] == 0)
		{
			if (i == 0 && team[i + 1] == 2)
				team[i + 1]--, team[i]++;
			else if (i == N && team[i - 1] == 2)
				team[i - 1]--, team[i]++;
			else
			{
				if (team[i - 1] == 2)
					team[i - 1]--, team[i]++;
				else if (team[i + 1] == 2)
					team[i + 1]--, team[i]++;
			}
		}
	}

	for (int i = 1; i <= N; i++)
		if (team[i] == 0)
			retire++;
	cout << retire;
}

Tip

첫번째 팀과 마지막 팀은 카약을 빌릴 수 있는 경우가 정해져 있다는 걸 감안하고 나머지 경우에 대해서 문제를 풀어나가면 된다. 카약이 파손당한 팀이 빌릴 수 있는 한 무조건 빌리는 탐욕법(그리디)를 이용해 푼다.