백준 2875. 대회 or 인턴 [성공]

1.문제 해결 전략

 이전 문제보다 조금 더 복잡해진 그리디 문제였다. 핵심은 모든 경우를 다 뒤져보면서 max값을 바꿔주는 것. 처음에는 너무 단순하게 생각해서 여성,남성에 인턴지원자들을 빼고 비교해서 대회에 나갈 수 있는 최대 조합을 찾으려 했는데, 생각을 해보니까 한 성별에서만 빼질수 있는게 아니라 두 성별에서 동시에 빼질수 있다는 것을 알아차렸다. 그래서 모든 경우를 어떻게 뒤질까 생각해 보니, for문을 돌면서 여성 -=i , 남성 -= (K-i) 를 통해 모든 경우에 대해 조사를 했고 각 경우에 대해서 만들어질 조합들을 max하였더니 문제를 풀 수 있었다.

 

2.작성 코드

#include <iostream>
#include <algorithm>
using namespace std;
int ans(int N, int M) {
	int a = 0;
	while (N - 2 >= 0 && M - 1 >= 0) {
		N -= 2;
		M -= 1;
		a++;
	}
	return a;
}
int main() {
	int N, M, K;
	int max = 0;
	cin >> N >> M >> K;
	// 팀을 최대한으로 만들어야 함.
	// 2인 1조,

	for (int i = 0; i <= K; i++) {
		int tempN = N; int tempM = M;
		if (tempN - i < 0 || tempM - (K - i) < 0)continue;
		tempN -= i;
		tempM -= (K - i);
		max = std::max(ans(tempN, tempM), max);
	}

	cout << max << endl;
	return 0;
}

3.걸린 시간 & 느낀점

30분 넘게 걸렸다. 순간적인 집중력이 많이 약한 것같다.. 풀던중 웹서핑도 하고.. 커피도 마시고 ..

느낀점은 그리드 문제가 단순 구현문제와 다를게 없다는 점? 단순 구현 문제에 포함되는 카테고리 같다.

아직까지는 함정 문제가 없어서 쉽게 풀었지만.. 그리드로 안풀리는 문제가 있다는 걸 언젠가 본적이 있기에

항상 조심해서 접근하는 중이다.