[백준(c)] 18511번: 큰 수 구성하기

18511번: 큰 수 구성하기

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 N보다 작거나 같은 자연수 중에서, K의 원소로만 구성된 가장 큰 수를 출력한다.

예제입력	예제출력
657 3	577
1 5 7

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int max = 0;

int pick(int* items, int itemSize, int* bucket, int bucketSize, int k, int n)
{
	int i, lastIndex, smallest, itemIndex, sum;
	int flag = 0;

	if (k == 0) {
		sum = 0;
		for (i = 0; i < bucketSize; i++) {
			sum *= 10;
			sum += items[bucket[i]];
		}
		//printf("%d\n", sum);
		if (sum > n)
			return -1;
		if (sum <= n)
			if (sum >= max)
				max = sum;
		return 0;
	}

	lastIndex = bucketSize - k - 1;

	//if (bucketSize == k)
		smallest = 0;
	//else
		//smallest = bucket[lastIndex];

	for (itemIndex = smallest; itemIndex < itemSize; itemIndex++) {
		bucket[lastIndex + 1] = itemIndex;
		flag = pick(items, itemSize, bucket, bucketSize, k - 1, n);
		if (flag == -1)
			break;
	}
	return 0;
}

int main(void)
{
	int n, itemSize, i, bucketSize = 0;
	int itemMax = 0, semiMax = 0;
	int* bucket;
	int* items;

	scanf("%d %d", &n, &itemSize);

	int nn = n;
	while (nn != 0) {
		nn /= 10;
		bucketSize++;
	}

	bucket = (int*)malloc(sizeof(int) * bucketSize);
	items = (int*)malloc(sizeof(int) * itemSize);
	for (i = 0; i < itemSize; i++) {
		scanf("%d", &items[i]);
		if (items[i] > itemMax)
			itemMax = items[i];
	}

	for (i = 0; i < bucketSize - 1; i++) {
		semiMax *= 10;
		semiMax += itemMax;
	}
	pick(items, itemSize, bucket, bucketSize, bucketSize, n);

	printf("%d\n", (max < semiMax) ? semiMax : max);
}