엘리스 코드 챌린지 1번 풀이

문제

엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.

예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.

오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

 

풀이: 백트래킹으로 숫자조합을 모든 경우의 수를 구해 값을 구한다

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int arr[10] = {0,};
int num[10] = {0,};
int visit[10] = {0,};

int lens = 0;
int value;
int mins = 10000000;

void func(int k) {
    if(k == lens) {
        int sum = 0;
        for(int i = 0; i < k; i++) {
            sum += arr[i] * pow(10, i);
        }
        
        if(sum > value && mins > sum) {
        	mins = sum;
		}
    }
    
    for(int i = 0; i < lens; i++){
    	if(visit[i]) continue;
    	
    	visit[i] = 1;
    	arr[k] = num[i];
    	func(k+1);
    	visit[i] = 0;
 	}
}

int main() {
    string str;
    


    cin >> str;
    
    value = stoi(str);

    lens = str.length();

    for(int i = 0; i < lens; i++) {
        num[i] = str[i] - 48;
    }

    func(0);
    
    cout << mins;
}