문제 개요
아이디어
대회할땐 못풀었다가 해설방송에서 a,b는 999이하니까 그냥 다 돌려보란말..듣고 품;
그냥 A 1~999 다 돌리면 시간초과나고, (vs에서도 시간 오래걸림)
s[0], s[1], s[2] 한자리/두자리/세자리수 중 무조건 시작값이 있으니까 그 세개로 돌렸음.
다 만들어서 비교하는거말고..파싱해서 보는건 어케하는건지 모르겠다.
교훈: 숫자가 작다면 브루트포스 알고리즘을 생각해보자.
코드
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<string.h>
#include<math.h>
#include<stack>
using namespace std;
string solve(int A, int B) {
string tmp = ""; string ret = "";
for (int i = A; i <= B; i++) {
tmp = to_string(i);
ret.append(tmp);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string S; cin >> S;
// A와 B는 1이상 999이하의 정수이므로
// 모든 경우의 수를 다 돌려보고 s와 같은지 체크한다
int A1 = S[0] - '0';
/* // 시간초과나는 부분
for (int A = 4; A <= 999; A++) {
for (int B = A; B <= 999; B++) {
string ret = solve(A, B);
// cout << A << " " << B << " " << tmp << "\n";
if (ret == S) {
cout << A << " " << B;
return 0;
}
}
}
*/
for (int B = A1; B <= 999; B++) {
string ret = solve(A1, B);
if (ret == S) {
cout << A1 << " " << B;
return 0;
}
}
int A2 = 10 * (S[0] - '0') + (S[1] - '0');
for (int B = A2; B <= 999; B++) {
string ret = solve(A2, B);
if (ret == S) {
cout << A2 << " " << B;
return 0;
}
}
int A3 = 100 * (S[0] - '0') + 10*(S[1] - '0') + (S[2] - '0');
for (int B = A3; B <= 999; B++) {
string ret = solve(A3, B);
if (ret == S) {
cout << A3 << " " << B;
return 0;
}
}
return 0;
}