문제 정보

백준 ( BOJ ) 1065

문제 풀이 : 탐색

문제 출처 : https://www.acmicpc.net/problem/1065

문제 풀이

문제를 딱 보면, 1부터 n까지 각 수들이 등차인지 비교하며 넘어가는 문제 같아 보입니다.

그러나 이 문제에서는 그 방식으로 해도 시간 초과가 나지 않을 테지만,

조금 생각의 방향을 돌려서 접근 해 볼 필요가 있습니다.

등차인지 아닌지 확인 하는 것이 아니라,

일부러 등차인 수들을 만들어 나가는 겁니다.

우선 1 ~ 99 는 모두 한 수 입니다.

두자리든 한자리든 그 차이는 같을 수밖에 없으니까요.

그리고 100~ 1000 까지를 구하면 되는데,

100 부터 시작해서, 100단위로 맨 앞자리를 기준으로 등차를 만들어 주면 됩니다.

111, 123, 135, 147, 등등 이런식으로 말이죠.

다만 생각해야 하는건, 987 도 등차라는 점입니다.

역순도 문제의 조건에 부합하니까요.

저같은 경우, set을 사용해서 한수인지 아닌지 저장 하도록 했습니다.

굳이 set이 아니라, 배열로 하여도 되고,

어떤 데이터 방식을 사용하여도 이 문제에서는 크게 차이 나지 않음으로,

자유롭게 사용 하셔도 될 듯 합니다.

코드

#include <iostream>
#include <set>

using namespace std;

int main() {
	int n = 1;
	int ob;
	int count = 0;
	cin >> ob;
	set <int> hansoo;
	for (; n < 100; n++) {
		hansoo.insert(n);
	}
	for (; n < 1000; n += 100) {
		for (int i = 0; n / 100 + i * 2 < 10; i++) {
			hansoo.insert(n + (n/100+i) * 10 + (n/100+i*2) );
		}
		for (int i = 0; n / 100 - i * 2 >= 0; i++) {
			hansoo.insert(n + (n / 100 - i) * 10 + (n / 100 - i * 2));
		}
	}
	for (auto a = hansoo.begin();  a != hansoo.end() && *a <= ob; a++) {
		count++;
	}
	cout << count;
	return 0;
}