[boj2599/c++] 짝 정하기

https://www.acmicpc.net/problem/2599

2599번: 짝 정하기

간단한데 안간단하고.. 더 라이트하게 푸는 방식도 있을 거 같은데 못찾겠음ㅠㅠ

풀이 방식은 처음에 O(n^2)으로 풀었다가 다른 분들 코드 참고해서 다른 식으로 O(n)으로 한번 더 해결!

 

먼저 O(n^2) 풀이는 다음과 같음

#include <iostream>

using namespace std;

int N;
pair<int, int> stud[3];
int ab, ac, ba, bc, ca, cb;

int main() {
	cin >> N;
	for (int i = 0; i < 3; i++) {
		cin >> stud[i].first >> stud[i].second;
	}
	if (stud[0].first > stud[1].second + stud[2].second || stud[1].first > stud[0].second + stud[2].second || stud[2].first > stud[0].second + stud[1].second) cout << 0;
	for (int i = 0; i < stud[0].first; i++) {
		ab = i;
		ac = stud[0].first - i;
		for (int j = 0; j < stud[0].second; j++) {
			ba = j;
			bc = stud[1].first - ba;
			ca = stud[0].second - ba;
			cb = stud[1].second - ab;
			if (ba+ca == stud[0].second && ab+cb == stud[1].second && ac+bc == stud[2].second) {
				cout << 1 << '\n';
				cout << ab << ' ' << ac << '\n';
				cout << ba << ' ' << bc << '\n';
				cout << ca << ' ' << cb << '\n';
				return 0;
			}
		}
	}
	cout << 0;
}

 

 

먼저 A학교 남학생 수를 가지고 B 학교 여학생 중 몇명이랑 짝지을 수 있는지를 고려해서 ab와 ac를 정하고(ab를 정하면 ac는 따라 나옴)

A학교 여학생 수를 가지고 B학교 남학생 중 몇명이랑 짝지을 수 있는지를 고려해서 ba를 잡으면 bc, ca, cb를 모두 정할 수 있음. 각각의 합이 학생수와 일치한다면 성공한걸로 보고 프린트함.

 

O(n) 풀이에서는 A학교 여학생 수를 가지고 ba를 정하는 것이 아니라 bc를 먼저 정해준다. 그 이유는 c는 c학교 여학생을 고를 수 없기 때문에 b는 일단 남아있는 c학교 여학생들 모두와 짝지어져야 한다. 그렇기 때문에 bc를 구하면 ba, ca cb를 모두 정리할 수 있다. 이때는 음수가 되는 경우가 있는지 확인한다면 성공여부를 판단할 수 있음!

#include <iostream>

using namespace std;

int N;
pair<int, int> stud[3];
int ab, ac, ba, bc, ca, cb;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < 3; i++) {
		cin >> stud[i].first >> stud[i].second;
	}
	if (stud[0].first > stud[1].second + stud[2].second || stud[1].first > stud[0].second + stud[2].second || stud[2].first > stud[0].second + stud[1].second) cout << 0;
	for (int i = 0; i < stud[0].first; i++) {
		ab = i;
		ac = stud[0].first - i;
		bc = stud[2].second - ac;
		ba = stud[1].first - bc;
		ca = stud[0].second - ba;
		cb = stud[1].second - ab;
		if (bc >= 0 && ba >=0 && ca >= 0 && cb >= 0) {
			cout << 1 << '\n';
			cout << ab << ' ' << ac << '\n';
			cout << ba << ' ' << bc << '\n';
			cout << ca << ' ' << cb << '\n';
			return 0;
		}
		
	}
	cout << 0;
}