[c++] codeground 연습문제'회문인 수의 합' (2018년도 SCPC 예선1차)

문제:www.codeground.org.     , practice/회문인 수의 합/

codeground

 

 

1번 아이디어(실패)

 

현재 수와 가장 가까운 회문의 수를 찾는 방법은, 두 수를 비교하여 작은 수를 그 자리에 대체하는 것으로 생각했었다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cnt;
vector<int> result;

void calculate(vector<int> num, int num_int){
    
    int check = 0;
    int Palindrome[5]={0,};
    
    if(cnt > 3){
        return;
    }
    
    // 앞뒤부터, 가운데로 오면서 비교
    int num_size = num.size();
    for(int i=0 ; i< num_size/2 ; i++){
        if(num[i] == num[num.size()-i-1]){
            Palindrome[i] = num[i];
            Palindrome[num.size()-i-1] = num[num.size()-i-1];
            check++;
        }
        else{
            if(num[i] > num[num.size()-i-1]){
                Palindrome[i] = num[num.size()-i-1];
                Palindrome[num.size()-i-1] = num[num.size()-i-1];
            }
            else{
                Palindrome[i] = num[i];
                Palindrome[num.size()-i-1] = num[i];
            }
        }
    }
    
    // 홀수인 경우, 정가운데 따로 처리
    if(num.size()%2 == 1){
        Palindrome[num.size()/2] = num[num.size()/2];
    }
    
    // 배열에 들어있는 값 int로(회문 수 구하기)
    int palindrome_int=0;
    for(int i=0 ; i< num_size ; i++){
        int tmp=1;
        for(int j=0 ; j< num_size-i-1 ; j++){
            tmp = tmp*10;
        }
        palindrome_int = palindrome_int + ( tmp * Palindrome[i] );
    }
    
    
    if(check == num_size/2){
        result.push_back(palindrome_int);
    }
    else{
        result.push_back(palindrome_int);
        num_int = num_int - palindrome_int;
        int tmp_num = num_int;
        vector<int> last_vec;
        while(tmp_num > 0){
            int remainder;
            remainder = tmp_num % 10;
            tmp_num = int(tmp_num/10);
            last_vec.push_back(remainder);
        }
        reverse(last_vec.begin(), last_vec.end());
        cnt++;
        calculate(last_vec, num_int);
    }
    
}



int main(int argc, char** argv)
{
    int T, test_case;

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {

        cnt = 1;
        result.clear();
        
        int input_int;
        vector<int> input_store;
        
        cin >> input_int;
        
        
        int tmp_num = input_int;
        while(tmp_num > 0){
            int remainder;
            remainder = tmp_num % 10;
            tmp_num = int(tmp_num/10);
            input_store.push_back(remainder);
        }
        reverse(input_store.begin(), input_store.end());
        
        
        calculate(input_store, input_int);
        
        
        
        cout << "Case #" << test_case+1 << endl;
        int result_size = result.size();
        if(cnt > 3){
            cout << "0" << endl;
        }
        else{
            cout << cnt;
            for(int i=0 ; i< result_size ; i++){
                cout << " " << result[i];
            }
            cout << endl;
        }
    }

    return 0;//Your program should return 0 on normal termination.
}

 

하지만 이는 9998과 같은 경우 예외가 생겼다.

위 방법을 사용하면 9998 = 8998 + 1000 + 0 + 0 + .... 가 되어 3개 이상의 수로 나누어지게 되고, 정답이 0이 출력이 되었다.

 

 

2번 아이디어 (실패)

 

실제 주어지는 입력값이 10000 이하의 수 하나이므로, 수를 하나씩 낮춰가며 모두 확인하여도 시간이 충분할 것이라는 생각이 들었다.

수를 하나씩 내려가며 비교를 진행하다, 회문인 수를 찾으면 다음으로 넘어가는 방법으로 진행하였다.

 

ex) 1234를 1씩 내려가며 회문인 수인지 확인하다가 1221을 마주하면, 다음 13으로 넘어가 다시 1씩 내려가며 회문인 수인지 확인한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cnt;
vector<int> result;

void calculate(vector<int> num, int num_int){
    
    int check = 0;
    int Palindrome[5]={0,};
    int new_num_int = num_int;
    
    if(cnt > 3){
        return;
    }
    
    int num_size = num.size();
    
    // 앞뒤부터, 가운데로 오면서 비교
    while(1){
        
        for(int i=0 ; i< num_size/2 ; i++){
            if(num[i] == num[num.size()-i-1]){
                check++;
            }
        }
        
        if(check == num_size/2){
            result.push_back(new_num_int);
            break;
        }
        else{
            new_num_int -= 1;
            int tmp_num = new_num_int;
            num.clear();
            while(tmp_num > 0){
                int remainder;
                remainder = tmp_num % 10;
                tmp_num = int(tmp_num/10);
                num.push_back(remainder);
            }
            reverse(num.begin(), num.end());
            
        }
        num_size = num.size();
        check = 0;
    }
    
    if(num_int == new_num_int){
        return;
    }
    else{
        cnt++;
        int next_num = num_int - new_num_int;
        int tmp_num = next_num;
        num.clear();
        while(tmp_num > 0){
            int remainder;
            remainder = tmp_num % 10;
            tmp_num = int(tmp_num/10);
            num.push_back(remainder);
        }
        reverse(num.begin(), num.end());
        
        calculate(num , next_num);
    }
    
}



int main(int argc, char** argv)
{
    int T, test_case;

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {

        cnt = 1;
        result.clear();
        
        int input_int;
        vector<int> input_store;
        
        cin >> input_int;
        
        
        int tmp_num = input_int;
        while(tmp_num > 0){
            int remainder;
            remainder = tmp_num % 10;
            tmp_num = int(tmp_num/10);
            input_store.push_back(remainder);
        }
        reverse(input_store.begin(), input_store.end());
        
        
        calculate(input_store, input_int);
        
        
        
        cout << "Case #" << test_case+1 << endl;
        int result_size = result.size();
        if(cnt > 3){
            cout << "0" << endl;
        }
        else{
            cout << cnt;
            for(int i=0 ; i< result_size ; i++){
                cout << " " << result[i];
            }
            cout << endl;
        }
    }

    return 0;//Your program should return 0 on normal termination.
}

하지만 이 방법도 9998에서 예외가 발생하였다.

실제 9888은 9009 + 989 처럼 두개의 수로 나와야 하지만, 위 방법을 사용하면 9998 = 9889 + 101 + 8 이 나왔다.

 

 

3번 아이디어(성공)

 

2번 아이디어를 조금 변형하여 회문인 수를 찾았다고 다음 수로 넘어가지 말고 끝까지 모든 수를 비교하였다.

 

ex) 1234를 1씩 내려가며 회문인 수인지 확인하다가 1221을 마주하면, 다음 13으로 넘어가 다시 1씩 내려가며 회문인 수인지 확인하고, 현재 함수는 계속해서 1220, 1119 .... 내려가며 회문인 수인지 확인한다.

 

현재 calculate함수에 입력된 값이 회문인 수라면 result vector를 초기화 하고, 재귀적으로 올라가며, 값들을 저장한다.

현재 회문의 수의 개수를 전역변수 cnt에 저장하고, 이보다 수가 많은 회문의 수의 조합의 경우는 고려하지 않는다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int cnt;
vector<int> result;


// int형을 vector형으로 바꿔준다.
vector<int> int_to_vec(int num){
    vector<int> v;
    while(num > 0){
        int remainder;
        remainder = num % 10;
        num = int(num/10);
        v.push_back(remainder);
    }
    reverse(v.begin(), v.end());
    return v;
}


// 숫자를 vector형과 int형으로 각각 매개변수를 통해 넘겨받는다.
// count를 이용하여 현재 수를 몇개까지 나눈 상태인지 확인한다.
// 회문의 수가 3 이상이거나, 현재 저장된 회문의 수보다 많은 경우는 넘어간다.
// num_int : 현재 입력받은 숫자.
// new_num_int : num_int를 하나씩 낮춰가며 찾은 회문의 수.
// 입력받은 수가 재귀적으로 거슬러 올라가며, 값을 result vector에 push하기 위해 int를 return한다.
int calculate(vector<int> num, int num_int, int count){
    
    int check = 0;
    int palindrome = num_int;
    
    if(count > 3 || count > cnt){
        return 0;
    }
    
    int num_size = num.size();
    
    // 숫자를 하나씩 낮춰가며 모두 확인한다.
    // 중간이 넘어가면 결국 중복이므로 절반까지만 비교한다.
    for(int j=0 ; j<= num_int/2 ; j++){
        
        // 앞뒤부터, 가운데로 오면서 비교
        for(int i=0 ; i< num_size/2 ; i++){
            if(num[i] == num[num.size()-i-1]){
                check++;
            }
        }
        
        // new_num_int가 회문의 수인 경우
        if(check == num_size/2){
            if(num_int == palindrome){ // 처음 입력받은 수가 회문의 수
                cnt = count;
                result.clear();
                result.push_back(palindrome);
                return 1;
            }
            else{                       // 수가 나누어졌음을 의미
                int next_num_int = num_int - palindrome;
                vector<int> next_num;
                
                next_num = int_to_vec(next_num_int);
                int tmp =calculate(next_num, next_num_int, count+1);
                if(tmp){
                    result.push_back(palindrome);
                    if(count != 1)      // 현재 재귀가 마지막이 아닐경우, 윗단계로 올라가도록 한다.
                        return 1;
                }
            }
        }
        
        palindrome -= 1;
        num.clear();
        num = int_to_vec(palindrome);
        
        num_size = num.size();
        check = 0;
    }
    
    return 0;
}





int main(int argc, char** argv)
{
    int T, test_case;

    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {

        cnt = 5;
        result.clear();
        
        int input_int;
        vector<int> input_store;
        
        cin >> input_int;
        
        input_store = int_to_vec(input_int);
        calculate(input_store, input_int, 1);
        
        
        
        cout << "Case #" << test_case+1 << endl;
        int result_size = result.size();
        if(cnt > 3){
            cout << "0" << endl;
        }
        else{
            cout << cnt;
            for(int i=result_size-1 ; i>= 0 ; i--){
                cout << " " << result[i];
            }
            cout << endl;
        }
    }
    return 0;//Your program should return 0 on normal termination.
}