취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 12347번 문제인 한수 2이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/12347

등차수열의 공차가 0이 아닌 한수는 길어봐야 10자리(9876543210)이고, 그 외의 한수는 한 가지 숫자가 반복되는 형태의 수밖에 없음을 관찰하자. 이 관찰을 이용하면 주어진 범위 내의 한수는 매우 적음을 발견할 수 있다.

따라서, ${10}^{18}$ 이하의 모든 한수를 생성하여 그 수가 범위 내에 포함되는지 판단하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;
typedef __int128 lll;

ll N, ans;

void func(int x, int y) {
	int d = y - x;
	lll val = x * 10 + y;
	while (val <= N) {
		ans++;
		y += d;
		if (y < 0 || y > 9) break;
		val = val * 10 + y;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 1; i < 10; i++) {
		if (i <= N) ans++;
		for (int j = 0; j < 10; j++) {
			func(i, j);
		}
	}
	cout << ans;
}