scpc Practice 회문인 수의 합

scpc Practice 회문인 수의 합

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include <algorithm>
#include<cmath>
using namespace std;
 
 
 
int Answer;
 
//숫자의 길이 확인하는 함수
int numlength(int num) {
    int length = 0;
    while (num) {
        num /= 10;
        length++;
    }
    return length;
}
 
//회문인지 확인하는 함수 
bool Pal(int num) {
    int length = numlength(num);
    vector<int> numArr(length);
    for (int i = length - 1; i >= 0; i--) {
        int a = (num % 10);
        num /= 10;
        numArr[i] = a;
    }
    for (int i = 0; i < length / 2; i++) {
        if (numArr[i] != numArr[length - 1 - i])
            return false;
    
    }
    return true;
 
}
 
int main(int argc, char** argv)
{
    int T, test_case;
    int n;
 
    cin >> T;
    for (test_case = 0; test_case < T; test_case++)
    {
 
        cin >> n;
        int temp = n;
        int length = 0;
    
        vector<int> Palind;
        //1부터 n까지 회문인 수 모두 Palind벡터에 저장
        for (int i = n; i >= 1; i--) {
            if (Pal(i)) {
                Palind.push_back(i);
            }
        }
        int Size = Palind.size();
        bool Check1 = false, Check2 = false, Check3 = false;
        vector<int> ans;
        //회문 1개 합으로 가능한 경우
        for (int i = 0; i < Size; i++) {
 
            if (n == Palind[i]) {
                Check1 = true;
                ans.push_back(n);
                break;
            }
        }
        //회문 2개 합으로 가능한 경우
        if (!Check1) {
            for (int i = 0; i < Size; i++) {
                for (int j = 0; j < Size; j++) {
                    if (n == Palind[i] + Palind[j]) {
                        Check2 = true;
                        ans.push_back(Palind[i]);
                        ans.push_back(Palind[j]);
                        break;
                    }
                }
                if (Check2)
                    break;
            }
        }
        //회문 3개 합으로 가능한 경우
        if (!Check1 && !Check2) {
            for (int i = 0; i < Size; i++) {
                for (int j = 0; j < Size; j++) {
                    for (int k = 0; k < Size; k++) {
                        if (n == Palind[i] + Palind[j] + Palind[k]) {
                            Check3 = true;
                            ans.push_back(Palind[i]);
                            ans.push_back(Palind[j]);
                            ans.push_back(Palind[k]);
                            break;
                        }
                    }
                    if (Check3) break;
                }
                if (Check3) break;
            }
        }
 
        cout << "Case #" << test_case + 1 << endl;
        if (!Check1 && !Check2 && !Check3)
            cout << 0 << endl;
        else {
            cout << ans.size() << " ";
            for (int i = 0; i < ans.size(); i++)
                cout << ans[i] << " ";
            cout << endl;
        }
        
    }
 
    return 0;
}

출처:https://www.codeground.org/practice/practiceProblemViewNew

내림차순으로 출력하라그랬는데 정렬을 안하고 출력해도 어떻게 잘 출력이 되네요... ㅎㅎ; 

큰숫자부터 빨리 break 걸어서 의도치않게 해결해버렸습니다

N은 회문의 갯수 

O(N^3)으로 풀어도 시간복잡도는 문제없이 해결이 가능합니다.