fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 21394 (C++) 숫자 카드
최초 업로드: 2025-09-28 17:24:23
최근 수정 시간: 2025-09-28 17:24:23
게시자: rlatjwls3333
카테고리: 백준
조회수: 10
# [Bronze I] 숫자 카드 [문제 링크](https://www.acmicpc.net/problem/21394) ## 문제 설명 <p>Albert는 총 n장의 숫자 카드를 가지고 있다. 각 숫자 카드는 1부터 9까지의 숫자가 하나씩 적혀있고, 6과 9는 카드를 회전하면 구분할 수 없기 때문에 Albert가 임의로 회전할 수 있다.</p> <p>구체적으로, x<sub>i</sub> 는 i가 적힌 숫자 카드의 개수라 하자 (따라서 x<sub>1</sub> + x<sub>2</sub> + ... + x<sub>9</sub> = n 이다).</p> <p>요즘 Albert는 집에서 혼자 카드 놀이를 하는데, 아래와 같은 방법으로 진행한다.</p> <ul> <li>먼저, n장의 카드를 임의의 순서로 좌-우로 나열한다. 이 때, Albert 마음대로 6이 적힌 카드나 9가 적힌 카드는 회전할 수 있다.</li> <li>이제 n장의 카드를 아래 규칙에 따라 한 장씩 가져와서 큰 수를 만든다. <ul> <li>처음에는 가장 좌측에 놓인 카드를 가져온다.</li> <li>다음에는 가장 우측에 놓인 카드를 가져와서 이전에 가져온 카드 우측에 둔다.</li> <li>이후로 계속해서 좌측과 우측에서 번갈아 카드를 가져와 그 직전에 가져온 카드 우측에 둔다.</li> </ul> </li> </ul> <p>n장의 카드를 모두 가져오고나면 길이가 n인 정수가 만들어지는데, Albert는 이 수의 값이 가장 크게 되도록 하고 싶다.</p> <p>예를 들어 n = 5 이고 Albert가 가진 카드가 [6, 6, 7, 8, 9]라 하자. 아래와 같이 세 가지 다른 방법으로 다섯 장의 카드를 좌측부터 우측으로 나열한 경우, Albert가 규칙대로 게임을 진행하여 만들 수 있는 수는 아래와 같다.</p> <ul> <li>6 6 7 8 9 순으로 나열한 경우: 가장 좌측의 6, 가장 우측의 9, 좌측에서 두 번째에 놓인 6, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 7이 적힌 카드를 순서대로 가져와 69687 을 만들 수 있다.</li> <li>9 9 7 8 9 순으로 나열한 경우: 가장 좌측의 9, 가장 우측의 9, 좌측에서 두 번째에 놓인 9, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 7이 적힌 카드를 순서대로 가져와 99987 을 만들 수 있다.</li> <li>9 7 9 8 9 순으로 나열한 경우: 가장 좌측의 9, 가장 우측의 9, 좌측에서 두 번째에 놓인 7, 우측에서 두 번째에 놓인 8, 그리고 중간에 놓인 9가 적힌 카드를 순서대로 가져와 99789 를 만들 수 있다.</li> <li>이 예제의 경우, 99987이 Albert가 만들 수 있는 가장 큰 수 이다.</li> </ul> <p style="text-align: center;"><img alt="" src="https://upload.acmicpc.net/aa6157b9-0c65-4ba5-9f53-4bc639f4cc17/-/preview/" style="height: 224px; width: 400px;"></p> <p>입력으로 n장의 숫자 카드가 주어졌을 때, 맨 처음 Albert가 카드를 어떻게 나열해야 가장 큰 수를 만들 수 있는지 찾아서 알려주자.</p> ## 입력 <p>첫 줄에 테스트 케이스의 수 T가 주어진다.</p> <p>각 테스트 케이스는 한 줄에 총 9개의 정수가 (x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>9</sub>) 공백으로 구분되어 주어진다.</p> ## 출력 <p>각 테스트 케이스에 대해 n장의 카드를 어떻게 나열해야하는지 (좌측부터 우측으로) 한 줄에 걸쳐 출력한다.</p> ## 풀이 6은 전부 9로 바꿔주고 큰수부터 앞뒤로 왔다갔다하며 배치하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int cnt[10]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { for(int i=1;i<=9;i++) cin >> cnt[i]; cnt[9]+=cnt[6]; cnt[6]=0; int len = accumulate(cnt, cnt+10, 0); vector<int> res(len); int l=0, r=len-1; for(int i=9, idx=0;i>=1;i--) { while(cnt[i]--) { if(idx++%2==0) res[l++]=i; else res[r--]=i; } } for(int e : res) cout << e << ' '; cout << '\n'; } } ```