BOJ 2599 짝 정하기 풀이

* 링크

BOJ 2599 짝 정하기

* 풀이

풀이는 간단하다. 출력해야할 값이 6개(3열 2행)인데 3개(2행)은 나머지 3개(1행)만 구하면 구할 수 있으므로 1행의 값들만 구하면 된다.

입력으로 들어오는 값을

$n$

$a \quad d$

$b \quad e$

$c \quad f$

라 하고, 

출력할 값을

$1$

$x \quad (a \, - \, x)$

$y \quad (b \, - \, y)$

$z \quad (c \, - \, y)$

라 하자.

a, b, c, d, e, f는 모두 상수이고 x, y, z만 구하면 된다.

이제 식을 구성해보자.

$a에서\, x명이\, e로,\, (a\, -\, x)명이\, f로\, 간다.\, 마찬가지로\, b에서\, y명이\, d로, (b\, -\, y)명이\,f로,\, c에서\, z명이\, d로\, (c\, -\, z)명이\, e로\, 간다.$

따라서,

$d = y + z$ 

$e = x + (c - z)$

$f = (a - x) + (b - y)$

이다.

변수 3개에 방정식이 3개라서 바로 상수가 나오나? 싶지만 마지막에 $c$에서 남학생을 여학생에 배분할 때에는 $a$와 $b$의 남학생을 배분하고 난 뒤 남은 여학생에 배분하면 되므로 사실 필요없는 식이다.

위 식을 $x$에 대해 정리해서 처음에 출력할 값이라고 말한 부분에 대입하여 주면

$1$

$x \quad (a \, - \, x)$

$(n \, - \, c - \, f \, - x) \quad (b \, - \, y)$

$(d \, - \, y) \quad (c \, - \, z)$

가 된다. 모든 $y$, $z$값을 $x$에 대해 완벽히 정리할 수도 있지만 식이 복잡해지므로 그냥 변수 하나씩 할당해서 쓰는게 더 편하다. 

이제 $x$만 구하면 모두 구할 수 있으므로 $x$를 결정해주어야 하는데 입력으로 들어오는 학생의 숫자가 100,000이하 이므로 그냥 0부터 100,000 까지 for문으로 다 돌려주면 된다.

* 코드

#include <bits/stdc++.h>
using namespace std;
 
#define INF (INT_MAX / 2)
typedef long long ll;
typedef pair<int, int> pii;
 
int n;
vector<pii> arr(3);
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < 3; i++) 
        scanf("%d %d", &arr[i].first, &arr[i].second);
 
    for (int i = 0; i <= arr[0].first; i++) {
        int x = i;
        int ax = arr[0].first - x;
        int y = n - arr[2].first - arr[2].second - x;
        int by = arr[1].first - y;
        int z = arr[0].second - y;
        int cz = arr[2].first - z;
 
        if ((x >= 0) && (y >= 0) && (z >= 0) &&
            (ax >= 0) && (by >= 0) && (cz >= 0)) {
            printf("1\n");
            printf("%d %d\n", x, ax);
            printf("%d %d\n", y, by);
            printf("%d %d\n", z, cz);
            return 0;
        }
    }
    printf("0\n");
    
    return 0;
}