728x90
반응형
1422번: 숫자의 신
문제
https://www.acmicpc.net/problem/1422
풀이
K개의 수를 N번 사용해 가장 큰 수를 만드는 문제다. 단, 모든 수는 한 번은 이용해야 한다.
1. K개의 수 정렬
연결했을 때 가장 큰 수를 만들기 위해서 말 그대로 연결했을 때 더 큰 수가 되도록 했다. 예를 들어 1, 10, 100이라면 1과 10을 비교할 때 1 + 10 = 110과 10 + 1 = 101을 비교하는 것이다. 이 경우엔 110이 더 크기 때문에 위치가 바뀌지 않는다. 이 기준만으로 정렬한 후 출력하면 K개의 수를 모두 사용할 수는 있지만 N번 사용할 수는 없다.
아래 16496번 큰 수 만들기 문제와 정렬 기준이 같다.
2. 남은 횟수만큼 출력할 수 정렬
그러면 N개의 수를 사용해 가장 큰 수를 만들려면 가장 적절한 수 하나를 N-K번 사용하는 것이다. 여기서 가장 적절한 수는 두 가지 기준을 세웠다. 1. 수의 길이가 가장 길 것 2. 길이가 같다면 연결했을 때 큰 수 로 정했다. 왜냐하면 수의 길이가 긴 수를 반복해서 쓸수록 더 큰 수가 만들어질 것이고, 길이가 같다면 더 큰 수가 적합하기 때문이다. 이 기준에 따라 정렬하면 배열의 가장 앞에 해당 수가 온다.
따라서 1번 과정에 따라 정렬된 배열에서 가장 큰 수가 되도록 원소 하나씩 출력하며 2번 과정에 의해 나온 가장 적절한 수가 출력될 차례에 이 수를 N-K번 출력하도록 코드를 작성했다. 그리고 만약 같은 수가 원래 여러 개 출력될 예정이었을 경우에 대비해 flag를 사용해 여러 번 반복하지 않도록 제한을 뒀다.
코드
#include <bits/stdc++.h>
using namespace std;
// 1번 과정 정렬 기준
bool compare(string a, string b) {
string ab = a + b;
string ba = b + a;
return ab > ba;
}
// 2번 과정 정렬 기준
bool cmp(string a, string b) {
if (a.size() == b.size()) {
string ab = a + b;
string ba = b + a;
return ab > ba;
}
return a.size() > b.size();
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int k, n, flag = 0;
cin >> k >> n;
vector<string> v(k), tmp;
for (int i = 0; i < k; i++)
cin >> v[i];
tmp = v;
sort(tmp.begin(), tmp.end(), compare); // 1번 과정 정렬
sort(v.begin(), v.end(), cmp); // 2번 과정 정렬
for (int i = 0; i < k; i++) {
if (tmp[i] == v[0] && !flag) {
for (int j = 0; j < n - k + 1; j++)
cout << tmp[i];
flag = 1;
} else
cout << tmp[i];
}
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 5972 택배 배송 (0) | 2023.02.20 |
---|---|
[백준 / BOJ] C++ 1427 소트인사이드 (0) | 2023.02.19 |
[백준 / BOJ] C++ 16496 큰 수 만들기 (0) | 2023.02.19 |
[백준 / BOJ] C++ 1330 두 수 비교하기 (0) | 2023.02.19 |
[백준 / BOJ] C++ 1316 그룹 단어 체커 (0) | 2023.02.19 |