SCPC 2018 1차 예선: 회문인 수의 합 (C++)

(문제 설명)

 

1001과 같은 수처럼 앞에서 읽은 것이 뒤에서 읽은 것과 같은 수를 회문인 수라고 한다.

 

1 <= n <= 10,000 인 정수 n이 주어질 때, 세 개 이하의 회문인 수의 합으로 n이 표현될 수 있는지 여부를 판단하는 문제이다.

 

예시로 그 수들을 쭉 구해보면 알 수 있는데, 몇개 되지 않는다.

 

따라서 초기에 모두 구해두고 O(n^3)으로 해결했다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
vector<int> v; //회문수 벡터
int res[3];
int fir(int n) {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == n) {
			cout << 1 << ' ' << v[i] << '\n';
			return 1;
		}
	}
	return 0;
}
int sec(int n) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			if (v[i] + v[j] == n) {
				cout << 2 << ' ' << v[j] << ' ' << v[i] << '\n';
				return 1;
			}
		}
	}
	return 0;
}
int thi(int n) {
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			for (int k = 0; k < v.size(); k++) {
				if (v[i] + v[j] + v[k] == n) {
					cout << 3 << ' ' << v[k] << ' ' << v[j] << ' ' << v[i] << '\n';
					return 1;
				}
			}
		}
	}
	return 0;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		int n;
		cin >> n;
		//모든 회문수 구하기
		
		for (int i = 1; i <= 10000; i++) {
			string str = to_string(i);
			int len = str.length();
			bool isCir = true;
			for (int j = 0; j < len/2; j++) {
				if (str[j] != str[len - 1 - j]) {
					isCir = false;
					break;
				}
			}
			if (isCir)
				v.push_back(i);
		}
		
		cout << "Case #" << t << '\n';
		if (fir(n) == 1)
			continue;
		else if (sec(n) == 1)
			continue;
		else if (thi(n) == 1)
			continue;
		else
            cout << 0 << '\n';
	}
	return 0;
}