알고리즘(C++) / 백준 2875 : 대회 or 인턴

2875

www.acmicpc.net/problem/2875

2875번: 대회 or 인턴

 

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

 

입력

첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),

 

출력

만들 수 있는 팀의 최대 개수을 출력하면 된다.

 

코드1

//2875 대회 or 인턴
#include <iostream>
using namespace std;

int main() {
	int N, M, K;
	//N: 여학생 수
	//M: 남학생 수 
	//K: 인턴쉽에 참여해야하는 인원
	cin >> N >> M >> K;

	int team = 0;

	if (N / 2 <= M){
		team = N / 2;
	}
	else if (N / 2 > M) {
		team = M;
	}
	//인턴쉽을 고려하지 않고 만들 수 있는 팀

	K = K - (N - team * 2) - (M - team);

	if (K > 0) {
		if (K % 3 == 0) {
			team -= K / 3;
		}
		else {
			team = team - (K / 3) - 1;
		}
	}

	cout << team << endl;

	return 0;
}

 

설명1

처음 문제를 접하고 어떻게 해결해 나가야할지 고민하였다. 이번 문제는 간단한 수학문제로 생각하고 코드를 구현할 수 있었다.

인턴쉽에 참여해야하는 인원을 생각하지 않고 여학생 수와 남학생 수만을 확인하여 몇개의 팀을 결성할 수 있는지 team 변수에 저장한다.

팀을 구성하고 남은 사람들을 K에서 빼준다. 그 후 K의 수가 남아있다면(0보다 크다면) 팀을 해체하여 인턴쉽에 참가하게 해야한다. 따라서 K를 나눴을때 나머지가 0이라면 team에서 몫을 빼주고, 다른 경우라면 - (K / 3) - 1해준다.

 

코드2

//2875 대회 or 인턴
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N, M, K;
	//N: 여학생 수
	//M: 남학생 수 
	//K: 인턴쉽에 참여해야하는 인원
	cin >> N >> M >> K;

	cout << min(min(N / 2, M), (N + M - K)/3) << endl;

	return 0;
}

 

설명2

간단하게 다음과 같이  O(1)으로 구현할 수 있다. 

세가지 경우로 나눠서 생각할 수 있다. 

1. N,M의 수가 비슷할 때 -> (N+M-K)/3
2. N이 M보다  K를 커버할만큼 많을 때 -> M
3. M이 N보다 K를 커버할만큼 많을 때 -> N/2

-> 뒤에 있는 부분들이 최솟값이 된다.

 

결과

 

고찰

코드를 두가지로 구현해보았다. 

첫번째 경우는 내가 구현한 코드이고 두번째 경우는 다른 사람들의 코드를 참고하여 구현하였다. 두번째 방법이 더 간단하고 구현하기도 쉽지만,, 바로 저런 방법이 생각나지는 않았다. 다른 사람들 코드도 많이 참고하여 좀 더 연습해봐야할 거 같다. 

백준 문제에서는 예제 입력이 한가지나 두가지의 케이스밖에 없어서 테스트하는데 한계가 있다. 다른 경우도 직접 입력하여 확인해봐야 할 거 같다.