[BOJ/C++] 22351 수학은 체육과목 입니다 3 (2021 UCPC 예선 A번)

문제 개요

아이디어

대회할땐 못풀었다가 해설방송에서 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;
}

위는 A 범위를 1~999 모두 돌린것, 아래는 3가지 경우로 나눠서 돌린것.