https://www.acmicpc.net/problem/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;
}
'알고리즘' 카테고리의 다른 글
[boj11140/Java] LOL (0) | 2023.07.17 |
---|---|
[boj2075/c++] N번째 큰 수 (0) | 2023.05.05 |
[boj11728/c++] 배열 합치기 (0) | 2023.05.04 |
[boj4963, boj15652/c++] 섬의 개수, N과 M(4) (0) | 2023.05.02 |
[boj9934/c++] 완전 이진 트리 (0) | 2023.05.01 |