백준 10597번 : 순열장난

문제 링크 : https://www.acmicpc.net/problem/10597

10597번: 순열장난

 

 

 문제설명 

 

띄어쓰기 없이 숫자가 주어지는데 이때 띄어쓰기를 적절히 활용하여 알맞은 수열로 복구 시키면 되는 문제 .

복구한 수열의 경우의수가 여러가지일경우 하나만 출력.

 

 알고리즘 

 

1. 숫자의 갯수로 최대값을 구할 수있다.

숫자의 길이가 10이상일 경우 

max_num = 숫자의길이 /2+ 9

숫자의 길이가 9 이하일 경우

max_num = 숫자의 길이

 

2. 입력은 string으로 받아서 나중에 stoi 함수를 통해서 문자열을숫자로 변환시켜줘야된다 

3. 숫자를 한자리수나 두자리수로분할 하여 재귀 함수로 돌려준다.

 

애초에 백트래킹 부분을 잘못 생각하여 한참 걸려 블로그를 참고하였습니다.

참고 블로그: https://hibee.tistory.com/179

 

 코드 

 

#include<iostream>
#include<string>
#include<vector>
 
using namespace std;
string str;
int max_num, len;
int arr[51];
vector<int>v;
 
 
void func(int n) {
    //마지막 수열까지 확인했다면 출력 .
    if (n == len) {
        for (int i = 0; i < max_num; i++) {
            cout << v[i] << " ";
        }
        //한번만 출력
        exit(0);
    }
    int num;
    string s = "";
    //숫자를 한자리수 , 두자리수로 분할 .
    for (int i = n; i <= n + 1; i++) {
        
        s = s + str[i];
        num = stoi(s);
        //백트래킹 부분. 
 
        //숫자가 max_num 보다 크면 볼필요없음
        if (num > max_num) continue; 
        //앞에 이미 나온 숫자는 확인할 필요 없음 
        if (arr[num])continue;        
        v.push_back(num);
        arr[num] = 1;
        func(i + 1);
        arr[num] = 0;
        v.pop_back();
 
    }
 
}
 
 
int main() {
    cin >> str;
    len = str.length();
 
    if (len > 9)
        max_num = 9 + (len - 9) / 2;
    else
        max_num = len;
 
    for (int i = 1; i <= 50; i++)arr[i] = 0;
 
    func(0);
}