[백준] 숫자의 신 (1422번)

문제

숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.

오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.

오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.

예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.

입력

첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.

출력

N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.

예제 입력 1 복사

3 3 3 2 7

예제 출력 1 복사

732

---

쉽게 생각하고 덤볐다가 고생한 문제다.

우선 K개의 수는 한 번씩 사용해야 하므로 정답 벡터에 다 넣는다.

입력을 받으며 여러번 넣을 수를 골라야 한다. 숫자의 길이가 같다면 첫 번째 수가 높은 수, 아니라면 길이가 더 긴 수를 골라야 한다. 9와 100이 있다면 100을 여러번 추가하는 게 더 큰 수를 만들 수 있을 것이다.

 

넣을 수를 골라 N개의 수를 정답 벡터에 넣었다면, 이제 정렬해서 출력만 하면 된다.

제일 고생한 부분이 정렬 부분이다. N개의 수는 길이도, 크기도 다르기 때문에 어떤 수를 먼저 고르는 게 큰 수를 만들 수 있는지 판별하기가 까다롭기 때문이다. 

cmp 함수를 처음엔 첫 번째 글자만 비교했다가, 길이도 비교했다가 여러 방법을 사용했는데, 아주 예전에 비슷한 문제를 풀었던 기억으로 꼼수가 생각났다. 

문자열로 a + b 와 b + a중 더 큰 수를 먼저 고르면 되는 것이다. 998 과 9989를 비교한다면 9989-998 이 998-9989보다 크기 때문에 9989를 먼저 고르는 것이다.

이렇게 cmp 함수까지 작성한 후엔 들어있는 수를 차례대로 출력하면 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%88%AB%EC%9E%90%EC%9D%98%20%EC%8B%A0%20(1422%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int N, K;
vector<string> ans;

bool cmp(string a, string b) {
	if (a + b > b + a)
		return true;
	return false;
}

int main()
{
	cin >> K >> N;
	string str = "";
	string tmp;
	for (int i = 1; i <= K; i++) {
		cin >> tmp;
		if (str.size() < tmp.size() || (str.size()==tmp.size() && str < tmp)) str = tmp;
		ans.push_back(tmp);
	}

	for (int i = 0; i < N - K; i++)
		ans.push_back(str);

	sort(ans.begin(), ans.end(), cmp);
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i];
}