fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 31493 (C++) Broken trophy
최초 업로드: 2025-11-02 02:17:34
최근 수정 시간: 2025-11-02 02:17:34
게시자: rlatjwls3333
카테고리: 백준
조회수: 9
# [Platinum IV] Broken trophy [문제 링크](https://www.acmicpc.net/problem/31493) ## 문제 설명 <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/50b1c1f5-67d1-4216-bfbe-087c76ea031f/-/preview/" style="width: 276px; height: 120px;"></p> <p>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.</p> <p>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$<sup>th</sup> 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.</p> <p>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$<sup>th</sup> line and $j$<sup>th</sup> column of your rectangle.</p> ## 입력 <p>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$.</p> ## 출력 <p>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$<sup>th</sup> line and $j$<sup>th</sup> column with the $k$<sup>th</sup> piece, the $j$<sup>th</sup> number on the $i$<sup>th</sup> output line should be the integer $k$.</p> <p>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.</p> ## 풀이 무조건 배치할 수 있게 입력이 주어진다고 했으니, 먼저 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'; } } ```