숫자의 신은 여러명이 있지만, 그 중에 자연수의 신은 오세준이다. 오세준은 자연수의 신으로 오래오래 살다가 어느 날 음수의 신과 전쟁을 하게 되었다. 오세준은 음수의 신 이다솜을 이기기위해서 큰 숫자를 만들기로 했다.
오세준은 지금 K개의 자연수를 가지고 있다. 오세준은 K개의 수 중에 정확하게 N개의 수를 뽑아내서 그 수를 붙여서 만들 수 있는 수중에 가장 큰 수를 만들고자 한다. 같은 수를 여러 번 이용해도 된다. 단, 모든 수는 적어도 한 번은 이용되어야 한다.
오세준이 현재 가지고 있는 K개의 수가 주어졌을 때, 이 수를 적어도 한 번 이상 이용해서 만들 수 있는 수 중에 가장 큰 수를 출력하는 프로그램을 작성하시오.
예를 들어 지금 오세준이 2, 3, 7 이라는 3개의 수를 가지고 있고, 4개의 수를 뽑아야 한다면, 7732를 만들면 가장 큰 수가 된다.
입력
첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 50보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보다 작거나 같은 자연수이다. 이 수는 중복되어 들어올 수 있다. 만약 중복되어서 들어오는 경우에는 각 수가 적어도 입력으로 주어진 만큼 이용되어야 한다는 소리다.
출력
N개의 수를 뽑아서 연결해서 만들 수 있는 가장 큰 수를 출력한다.
예제 입력 1
3 3 3 2 7 |
예제 출력 1
732 |
예제 입력 2
2 4 4 7 |
예제 출력 2
7774 |
예제 입력 3
3 4 1 10 100 |
예제 출력 3
110100100 |
예제 입력 4
4 9 4 4 4 4 |
예제 출력 4
444444444 |
예제 입력 5
3 3 1 1 2 |
예제 출력 5
211 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int compare(char *a,char *b)
{
int len_a=strlen(a), len_b=strlen(b);
char *a_first=NULL, *b_first=NULL;
if(len_a<len_b)
{
for(int i=0;i<len_b;i++)
if(a[i%len_a]<b[i])
return 1;
else if(a[i%len_a]>b[i])
return -1;
}
else
{
for(int i=0;i<len_a;i++)
if(a[i]<b[i%len_b])
return 1;
else if(a[i]>b[i%len_b])
return -1;
}
a_first=(char *)calloc(len_a+len_b,sizeof(char));
strcpy(a_first,a);
strcat(a_first,b);
b_first=(char *)calloc(len_a+len_b,sizeof(char));
strcpy(b_first,b);
strcat(b_first,a);
for(int i=0;i<len_a+len_b;i++)
if(a_first[i]<b_first[i])
{
free(a_first);
free(b_first);
return 1;
}
else if(a_first[i]>b_first[i])
{
free(a_first);
free(b_first);
return -1;
}
free(a_first);
free(b_first);
return 1;
}
int main(void)
{
int N, K, num, max=0;
char **list=NULL;
scanf("%d%d", &K, &N);
list=(char **)malloc(N*sizeof(char *));
for(int n=0;n<N;n++)
list[n]=(char *)calloc(11,sizeof(char));
for(int k=0;k<K;k++)
{
scanf("%d", &num);
max=num>max?num:max;
sprintf(list[k],"%d", num);
}
for(int i=K;i<N;i++)
sprintf(list[i],"%d", max);
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
if(compare(list[i],list[j])>0)
{
char temp[11]={'\0', };
strcpy(temp,list[i]);
strcpy(list[i],list[j]);
strcpy(list[j],temp);
}
for(int n=0;n<N;n++)
printf("%s", list[n]);
printf("\n");
for(int n=0;n<N;n++)
free(list[n]);
free(list);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 1759번: 암호 만들기 (0) | 2023.01.31 |
---|---|
<백준 알고리즘> 5557번: 1학년 (0) | 2023.01.31 |
<백준 알고리즘> 16496번: 큰 수 만들기 (0) | 2023.01.30 |
<백준 알고리즘> 14888번: 연산자 끼워넣기 (0) | 2023.01.27 |
<백준 알고리즘> 14889번: 스타트와 링크 (0) | 2023.01.27 |