백준 2365 (C++) 숫자판 만들기

최초 업로드: 2025-04-24 12:10:51

최근 수정 시간: 2025-07-25 09:09:05

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 숫자판 만들기

#### [문제 링크](https://www.acmicpc.net/problem/2365)

## 문제 설명

<p>가로의 크기와 세로의 크기가 각각 N인 숫자판이 있다. 숫자판의 각 칸에는 음 아닌 정수들만 들어갈 수 있고 각 행과 각 열의 합이 미리 주어진다고 하자. N=2 인 경우의 예가 다음에 있다.</p>

<p>위 그림에서 숫자판 옆의 수는 해당하는 행에 들어가는 숫자의 합을 나타내며, 숫자판 아래의 수는 해당하는 열에 들어가는 숫자의 합을 나타낸다. 이제, 숫자판에 주어진 합과 일치하도록 수를 넣으려고 한다. 합이 일치되도록 숫자를 넣는 방법은 여러 가지 있을 수 있으며 위의 예에 대해 서로 다른 형태를 3가지만 보이면 다음과 같다.</p>

<p>이 문제에서는 가능한 여러 가지 형태중 숫자판에 들어가는 최대 숫자의 값을 최소로 하는 형태를 찾고자 한다. 그러므로, 위의 예에서는 최대 숫자가 6 인 형태가 원하는 답이다. 이 문제를 해결하는 프로그램을 작성하시오. </p>

## 입력

<p>입력의 첫째 줄에는 행(열)의 크기 N이 주어진다(1 ≤ N ≤ 50). 둘째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1행부터 N행까지의 합을 차례대로 나타낸다. 셋째 줄에는 N개의 정수가 주어진다. 주어지는 정수는 1열부터 N열까지의 합을 차례대로 나타낸다. 합을 나타내는 각 정수는 0 이상 10000 이하이다. 숫자판을 구성할 수 없는 입력은 주어지지 않는다고 가정한다.</p>

## 출력

<p>첫 줄에는 배정된 수들중 최댓값을 출력한다. 둘째 줄부터 (N+1)째줄까지 각 행에 배정된 수들을 한 줄에 한 행씩 출력한다. 배정되는 각각의 정수는 0 이상이어야 한다. </p>

## 풀이
#### 행을 source와 연결하고, 열을 sink와 연결하여, 행과 열 사이의 용량을 이분 탐색하여 가능한 최소로 만들면 된다. source와 행 사이의 용량은 각 행의 숫자의 합이고, 열과 sink 사이의 용량은 각 열의 숫자의 합이다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 102;
const int S = MAX-2;
const int E = MAX-1;

int n, res[50][50], f[MAX][MAX], c[MAX][MAX], prv[MAX];
vector<vector<int>> conn(MAX);

void flow(int maxFlow) {
    memset(f, 0, sizeof f);
    for(int i=0;i<n;i++) {
        for(int j=n;j<2*n;j++) {
            c[i][j] = maxFlow;
        }
    }

while(true) {
        memset(prv, -1, sizeof prv);
        queue<int> q; q.push(S);
        while(!q.empty() && prv[E]==-1) {
            int cur = q.front(); q.pop();
            for(int next:conn[cur]) {
                if(c[cur][next]-f[cur][next]>0 && prv[next]==-1) {
                    prv[next]=cur;
                    if(next==E) break;
                    q.push(next);
                }
            }
        }
        if(prv[E]==-1) break;

int flow=INF;
        for(int i=E;i!=S;i=prv[i]) {
            flow = min(flow, c[prv[i]][i]-f[prv[i]][i]);
        }
        for(int i=E;i!=S;i=prv[i]) {
            f[prv[i]][i] += flow;
            f[i][prv[i]] -= flow;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;

// 행들을 S에 부착
    for(int i=0;i<n;i++) {
        cin >> c[S][i];
        conn[i].push_back(S);
        conn[S].push_back(i);
    }

// 열들을 E에 부착
    for(int i=n;i<2*n;i++) {
        cin >> c[i][E];
        conn[i].push_back(E);
        conn[E].push_back(i);
    }

// 행과 열 사이의 연결
    for(int i=0;i<n;i++) {
        for(int j=n;j<2*n;j++) {
            conn[i].push_back(j);
            conn[j].push_back(i);
        }
    }

int left=0, right=10000;
    while(left<right) {
        int mid = (left+right)/2;
        flow(mid);

// chk==true : 지금 mid로 행렬을 만들 수 있음 (mid가 아무리 높아봐야 최대값)
        // chk==false : 지금 mid로 행렬을 만들 수 없음 (최댓값이 mid보단 커야함)
        bool chk=true;
        for(int i=n;i<2*n;i++) {
            if(c[i][E]!=f[i][E]) {
                chk=false;
                break;
            }
        }

if(chk) right = mid;
        else left = mid+1;
    }

// left, right : 행렬에서 등장하는 최종 최댓값
    flow(left);
    cout << left << '\n';

// f[i][j] : i번 행에서 j-n번 열 사이의 플로우 (i번 행과 j-n번 열이 만나는 지점)
    for(int i=0;i<n;i++) {
        for(int j=n;j<2*n;j++) {
            cout << f[i][j] << ' ';
        }
        cout << '\n';
    }
}
```