[백준/BOJ] 2956 대칭 행렬 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/2956

[설명]
symmetric이면서 사전순으로 가장 앞서는 행렬의 특정 열들을 출력하는 문제이다.

만약 어떤 알파벳의 개수가 홀수라면 대각성분이 되어야 한다. 이를 고려하여 개수가 홀수인 알파벳의 수가 N보다 크다면 “IMPOSSIBLE”을 출력하면 된다.

행렬 자체를 만든다고 생각하면 30000*30000이므로 시간 안에 해결할 수 없을 것이다. 따라서 출력할 열들을 미리 받아서 그 열에 해당하는 공간만 채우면 된다.

먼저 대각성분을 고려해보자. 대각성분에는 개수가 홀수인 알파벳은 무조건 들어가야 한다. 따라서 남은 열의 개수와 남은 홀수 알파벳의 개수를 비교해 짝수 알파벳을 넣어도 되는지 아닌지를 판단할 수 있다. 그리고 넣을 수 있을 때, 짝수 알파벳을 다음 대각성분에도 집어넣어야 짝수임을 유지할 수 있다. 이후 홀수 알파벳이 나온다면 짝수 알파벳이 차있으므로 다음 대각성분에 추가한다. 만약 비어있는데 넣을 수 없다면 홀수인 다음 알파벳을 넣어주면 된다.

나머지 부분을 채워보자. 남은 알파벳의 개수를 한 행의 대각성분 뒷부분에 모두 채울 수 있는지 없는지를 판단한다. 채울 수 있다면 채우고 이 수를 빼주면 된다. 못 채운다면 다음 알파벳에서 이를 반복해주면 된다.

97퍼센트에서 틀렸다면 아래와 같은 반례 때문일 것이다.

[반례]

input:
2 3
A 2
Z 1
Q 1
2
1 2

answer:
QA
AZ

[코드]

#include<iostream>
#include<unordered_map>
#include<algorithm>
using namespace std;

struct Info {
	char alp;
	int cnt;
};

bool cmp(const Info& a, const Info& b) {
    return a.alp < b.alp;
}

Info info[26];
int print_col[51];
unordered_map<int, int> um;
char arr[51][30001], diagonal[30001];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k, odd = 0, i, j, p, ind = 0; cin >> n >> k;
	for (i = 0; i < k; i++) {
		cin >> info[i].alp >> info[i].cnt;
		if (info[i].cnt % 2 == 1) odd++;
	}
	cin >> p;
	for (i = 0; i < p; i++) {
		cin >> print_col[i];
        print_col[i]--;
		um[print_col[i]] = i + 1;
	}
	if (odd > n) {
		cout << "IMPOSSIBLE";
		return 0;
	}
    sort(info, info + k, cmp);
    for (i = 0; i < n; i++) {
        while (info[ind].cnt == 0) ind++;
        if (!diagonal[i]) {
            if (info[ind].cnt % 2 == 1) {
                odd--;
                info[ind].cnt--;
                diagonal[i] = info[ind].alp;
                if (um.count(i)) arr[um[i]][i] = info[ind].alp;
            }
            else if (n - i - 1 > odd) {
                info[ind].cnt -= 2;
                diagonal[i] = info[ind].alp;
                if (um.count(i)) arr[um[i]][i] = info[ind].alp;
                diagonal[i + 1] = info[ind].alp;
                if (um.count(i + 1)) arr[um[i + 1]][i + 1] = info[ind].alp;
            }
            else {
                int temp = ind;
                while (info[temp].cnt % 2 == 0) temp++;
                info[temp].cnt--;
                odd--;
                diagonal[i] = info[temp].alp;
                if (um.count(i)) arr[um[i]][i] = info[temp].alp;
            }
        }
        else if (info[ind].cnt % 2 == 1) {
            odd--;
            info[ind].cnt--;
            diagonal[i + 1] = info[ind].alp;
            if (um.count(i + 1)) arr[um[i + 1]][i + 1] = info[ind].alp;
        }
        if (info[ind].cnt / 2 >= n - i - 1) {
            info[ind].cnt -= 2 * (n - i - 1);
            for (j = 0; j < p; j++) {
                if (print_col[j] > i)  arr[um[print_col[j]]][i] = info[ind].alp;
            }
            if (um.count(i)) {
                for (j = i + 1; j < n; j++) arr[um[i]][j] = info[ind].alp;
            }
            if (info[ind].cnt == 0) ind++;
        }
        else {
            int temp = ind, need = n - i - 1, start = i + 1;
            while (need) {
                if (info[temp].cnt / 2 >= need) {
                    info[temp].cnt -= 2 * need;
                    for (j = 0; j < p; j++) {
                        if (print_col[j] >= start) arr[um[print_col[j]]][i] = info[temp].alp;
                    }
                    if (um.count(i)) {
                        for (j = start; j < n; j++) arr[um[i]][j] = info[temp].alp;
                    }
                    need = 0;
                }
                else {
                    for (j = 0; j < p; j++) {
                        if (print_col[j] >= start + info[temp].cnt / 2) break;
                        if (print_col[j] >= start) arr[um[print_col[j]]][i] = info[temp].alp;
                    }
                    if (um.count(i)) {
                        for (j = start; j < start + info[temp].cnt / 2; j++) arr[um[i]][j] = info[temp].alp;
                    }
                    need -= info[temp].cnt / 2;
                    start += info[temp].cnt / 2;
                    info[temp].cnt -= info[temp].cnt / 2 * 2;
                    temp++;
                }
            }
        }
	}
	for (i = 0; i < n; i++) {
		for (j = 1; j <= p; j++) cout << arr[j][i];
		cout << '\n';
	}
}