문제
https://www.acmicpc.net/problem/2992
풀이 방법
사실 수의 크기 제한이 작기 때문에 제약 사항에 주어진 모든 수를 파악해도 되지만, 그렇게 하면 백트레킹의 의미가 없기 때문에 필요하지 않은 가지는 치면서 진행되도록 코드를 작성하였다.
정확히는, 일단 제시된 숫자보다 작지 않고, 같거나 큰 숫자만 보도록 코드를 짯다. 먼저 앞 자리가 같은 경우에는 자리수가 같거나 커야하고 앞의 자리들이 큰 경우에는 뒤의 자리는 아무 숫자나 와도 상관 없다. 하지만 이때 사용하는 숫자는 원래 숫자를 구성했던 숫자들이여야 한다
따라서 해당하는 프로그램을 짜면 처음에 완성된 숫자는 같은 숫자일 것이고 그다음에 완성되는 숫자는 같은 숫자보다 조금 큰 정답일 것이다.
시간복잡도는 주어진 숫자의 순열이므로 모두 다를 때인 O(digit!)이 최대 인데 digit <= 6 이므로 시간내에 충분히 돌아간다.
실수
- 처음에 각 자리의 숫자를 떼어내는 방법에 대해 별다른 생각없이 진행해서 생각보다 많은 시간을 소요하였다.
- 또한 짠 코드도 운이 좋게 맞았지 내가 의도한 대로 작동하지 않은 코드도 존재하였다.
처음 적은 코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;
int input, result;
vector<int> each_digit(10, 0); // 각 숫자의 개수를 저장한 vector
vector<int> each_result(6, 0);
bool solution(int remain_num) {
if (input < result && remain_num == 0) { // 0에 도달했을때 입력보다 크면 성공, vector에 저장하여 출력
return true;
}
else {
for (int i = 0; i < 10; i++) {
if (each_digit[i] != 0 && ((input / (int)pow(10, remain_num - 1) > result) || (input / (int)pow(10, 7 - remain_num) % (int)pow(10, remain_num)) <= i)) {
result = result * 10 + i;
each_digit[i]--;
if (solution(remain_num - 1)) {
each_result[6 - remain_num] = i;
return true;
}
result = result / 10;
each_digit[i]++;
}
}
return false;
}
}
int main() {
int temp, digit = 0;
scanf("%d", &temp);
input = temp;
while (temp != 0){ // 입력 값을 각 자리 수 대로 쪼개서 필요한 정보 저장
each_digit[temp % 10]++;
temp = temp / 10;
digit++;
}
if (!solution(digit)) { // false이면 존재하지 않음, 0을 출력
printf("0");
}
else {
int i = 0;
for (; i <= each_result.size(); i++) { // true이면 존재, 역순으로 출력
if (each_result[i] != 0) {
break;
}
}
for (; i < each_result.size(); i++) { // true이면 존재, 역순으로 출력
printf("%d", each_result[i]);
}
}
return 0;
}
수정한 코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;
int input, result = 0;
vector<int> each_digit(10, 0); // 각 숫자의 개수를 저장한 vector
vector<int> each_result(6, 0); // 결과를 저장하는 vector
bool solution(int remain_num) { // 가장 맨 앞자리부터 가장 뒷자리까지 진행하는 재귀함수, remain_num은 남은 자리 수를 의미함
if (input < result && remain_num == 0) { // 0에 도달했을때 입력보다 크면 성공, vector에 저장하여 출력
return true;
}
else {
for (int i = 0; i < 10; i++) {
if (each_digit[i] != 0 // 숫자 i의 개수가 0이 아니고
&& ((input / (int)pow(10, remain_num - 1) > result)
|| (input % (int)pow(10, remain_num)) / (int)pow(10, remain_num - 1) <= i)) { // 이 부분 처음에 잘 못 적음
result = result * 10 + i;
each_digit[i]--;
if (solution(remain_num - 1)) { // return이 true이면 (마지막까지 도달했으면) 값을 저장
each_result[6 - remain_num] = i;
return true;
}
// 아니면 원상태로 복귀
result = result / 10;
each_digit[i]++;
}
}
// 모든 경우가 안됬으면 다시 뒤로 감
return false;
}
}
int main() {
int temp, digit = 0;
scanf("%d", &temp);
input = temp;
while (temp != 0) { // 입력 값을 각 자리 수 대로 쪼개서 각 숫자의 개수 저장
each_digit[temp % 10]++;
temp = temp / 10;
digit++;
}
if (!solution(digit)) { // false이면 존재하지 않음, 0을 출력
printf("0");
}
else {
int i = 0;
for (; i <= each_result.size(); i++) { // true이면 존재, 역순으로 출력 (맨 앞자리가 0이 아닌 수가 나올 때 까지 생략)
if (each_result[i] != 0) {
break;
}
}
for (; i < each_result.size(); i++) { // true이면 존재, 역순으로 출력
printf("%d", each_result[i]);
}
}
return 0;
}
기록용 블로그