https://www.acmicpc.net/problem/1040

문제

문제
정수 N이 주어진다. N보다 크거나 같은 수 중에, K개의 서로 다른 숫자로 이루어진 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 N과 K가 주어진다. N은 1018보다 작거나 같은 자연수이다. K는 10보다 작거나 같은 자연수이다.

출력
첫째 줄에 문제의 정답을 출력한다.

예제 입력 1
47 1
예제 출력 1
55

🤔첫 생각

알고리즘 문제해결 전략의 웨브바짐과 상당히 유사한 문제라고 느껴져서 비슷한 방식으로 풀면 되겠다고 느껴졌다. N의 길이가 K보다 클때와 그렇지 않을 때를 구분하고 재귀함수를 통해 문제를 풀때 앞에서 선택한 숫자들이 어떤것인지와 현재 몇 번째 숫자를 결정하고 있는지에 따라서 결과값이 결정된다는 점에서 DP를 적용하면 된다고 생각했다.

👏코드

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<math.h>

using namespace std;

int digits[19], len, K;
long long N;
string cache[1 << 11][19][2];

void calDigit() {
	long long num = N;

	while (num > 0) {
		digits[len++] = num % 10;
		num /= 10;
	}

	for (int s = 0, e = len - 1; s < e; s++, e--) {
		int tmp = digits[s];
		digits[s] = digits[e];
		digits[e] = tmp;
	}
}

string ans(int idx, int taken, int takenCnt, int pass) {
	if (idx == len)
		return takenCnt == K ? "" : "111111111111111111111111111111111";

	string& ret = cache[taken][idx][pass];

	if (!(ret.empty()))
		return ret;
	
	for (int d = (pass == 1 ? 0 + (idx == 0) : digits[idx]); d < 10 + (idx == 0); d++) {
		int newPass = pass || d > digits[idx];
		
		if (d == 10) {
			len += 1;
			ret = to_string(1) + ans(idx + 1, taken | (1 << 1), takenCnt + !(taken & (1 << 1)), 1);
		}
		else
			ret = to_string(d) + ans(idx + 1, taken | (1 << d), takenCnt + !(taken & (1 << d)), newPass);
		
		if (ret.size() < 30)
			return ret;
	}
	return ret;
}

int main(void) {
	int p = 0;

	cin >> N >> K;
	
	calDigit();
	
	if (len < K) {
		len = K;
		p = 1;
	}

	cout << ans(0, 0, 0, p);
	
	return 0;
}

😀후기

이 문제를 처음 봤던 것은 알고리즘을 공부하기 전인 4개월 전 이었다. 그때는 그저 N부터 시작해서 구성하는 숫자가 K인지를 판단하며 증가시키는 식으로 제출했던 기록이 남아있다. 하지만 이는 당연히 시간초과가 뜬다. 과거에는 풀 수 없었던 문제를 이제는 풀 수 있게 되었으니 과거보다는 현재가 더 발전한 형태가 아닐까 싶다.