백준 31493 (C++) Broken trophy

최초 업로드: 2025-11-02 02:17:34

최근 수정 시간: 2025-11-02 02:17:34

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] Broken trophy

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

## 문제 설명

Coming back home after triumphally winning your long-coveted trophy, you discover that it was shattered to pieces in your trunk. It just remains to repair it.

Your trophy had the shape of a rectangle of size $3 \times N$, for some integer $N \ge 1$, thereby consisting of $3$ lines and $N$ columns, containing a total of $3N$ unit squares. It was broken into $K$ pieces, the $k$th piece being a rectangle of size $A_k \times B_k$ for some integers $A_k$ and $B_k$ such that $1 \le A_k \le B_k \le 3$. Such pieces may have been rotated, or even flipped, in the havoc that is your trunk.

As the first step towards repairing your trophy, you should reassemble them in the form of a rectangle of size $3 \times N$. More precisely, you have drawn, on a sheet of paper, a $3 \times N$ rectangle on which you will place your $K$ pieces, and you need to know, for all integers $i \le 3$ and $j \le N$, which piece will cover the unit square on the $i$th line and $j$th column of your rectangle.

## 입력

The input consists of three lines, each one containing space-separated integers. The first line contains the numbers $K$ and $N$. The second line contains the numbers $A_1, A_2, \dots , A_K$. The third line contains the numbers $B_1, B_2, \dots, B_K$.

## 출력

The output should contain three lines, each one consisting of $N$ space-separated integers. If you plan to cover the unit square on the $i$th line and $j$th column with the $k$th piece, the $j$th number on the $i$th output line should be the integer $k$.

In case there are several ways to reassemble your pieces in the form of a rectangle of size $3 \times N$, every output representing one of these ways is considered correct.

## 풀이
무조건 배치할 수 있게 입력이 주어진다고 했으니, 먼저 2*2 블럭을 일렬로 배치하고 나머지 틈을 3*1 2*1 1*1을 이용하여 3*M 직사각형이 되도록 만듭니다. 그 후 남는 공간을 사용하지 않은 블럭으로 채워주면 됩니다.

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

int res[3][100'000], input[300'000][2];

vector<vector<int>> cnt(6); // 2*2, 3*1, 2*1, 1*1, 3*2, 3*3

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int k, n; cin >> k >> n;
 for(int i=0;i<k;i++) cin >> input[i][0];
 for(int i=0;i<k;i++) cin >> input[i][1];
 for(int i=0;i<k;i++) {
 if(input[i][0]==2 && input[i][1]==2) cnt[0].push_back(i+1);
 else if(input[i][0]==3 && input[i][1]==1 || input[i][0]==1 && input[i][1]==3) cnt[1].push_back(i+1);
 else if(input[i][0]==2 && input[i][1]==1 || input[i][0]==1 && input[i][1]==2) cnt[2].push_back(i+1);
 else if(input[i][0]==1 && input[i][1]==1) cnt[3].push_back(i+1);
 else if(input[i][0]==2 || input[i][1]==2) cnt[4].push_back(i+1);
 else cnt[5].push_back(i+1);
 }

int line0=0, line1=0, line2=0;
 while(!cnt[0].empty()) {
 res[1][line1]=res[1][line1+1]=cnt[0].back();
 res[2][line2]=res[2][line2+1]=cnt[0].back();
 cnt[0].pop_back();
 line1+=2;
 line2+=2;
 }
 while(line0<line1) {
 if(line0+3<=line1 && !cnt[1].empty()) {
 res[0][line0]=res[0][line0+1]=res[0][line0+2]=cnt[1].back();
 cnt[1].pop_back();
 line0+=3;
 } else if(line0+2<=line1 && !cnt[2].empty()) {
 res[0][line0]=res[0][line0+1]=cnt[2].back();
 cnt[2].pop_back();
 line0+=2;
 } else {
 res[0][line0]=cnt[3].back();
 cnt[3].pop_back();
 line0++;
 }
 }
 while(!cnt[1].empty()) {
 res[0][line0++]=res[1][line1++]=res[2][line2++]=cnt[1].back();
 cnt[1].pop_back();
 }
 while(!cnt[2].empty()) {
 if(cnt[2].size()>=3) {
 for(int i=0;i<3;i++) {
 res[i][line0]=res[i][line0+1]=cnt[2].back();
 cnt[2].pop_back();
 }
 line0 = line1 = line2 = line0+2;
 } else {
 res[0][line0++]=res[1][line1++]=cnt[2].back(); cnt[2].pop_back();
 res[2][line2++]=cnt[3].back(); cnt[3].pop_back();
 }
 }
 while(!cnt[3].empty()) {
 for(int i=0;i<3;i++) {
 res[i][line0]=cnt[3].back();
 cnt[3].pop_back();
 }
 line0++;
 }
 while(!cnt[4].empty()) {
 for(int i=0;i<3;i++) {
 for(int j=0;j<2;j++) res[i][j+line0]=cnt[4].back();
 }
 line0+=2;
 cnt[4].pop_back();
 }
 while(!cnt[5].empty()) {
 for(int i=0;i<3;i++) {
 for(int j=0;j<3;j++) res[i][j+line0]=cnt[5].back();
 }
 line0+=3;
 cnt[5].pop_back();
 }
 for(int i=0;i<3;i++) {
 for(int j=0;j<n;j++) cout << res[i][j] << ' ';
 cout << '\n';
 }
}
```