BOJ 1065 - 한수

문제 링크

문제#

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.

입력#

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

출력#

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

풀이#

한수인지 판별할 때 1자리와 2자리 수는 무조건 조건을 만족한다. 세 자리 수부터는 각 자리의 차이가 일정한지만 보면 되므로, 백의 자리와 십의 자리 차이, 십의 자리와 일의 자리 차이를 비교하면 된다.

코드는 1부터 N까지 차례대로 확인하면서 조건을 만족하는 수를 세는 방식이다. 입력 범위가 크지 않아서 복잡한 수학식보다 각 수를 자리수로 분해해 직접 검사하는 쪽이 더 단순하고 안전하다.

코드#

#include <iostream>
using namespace std;
 
int AP(int n) {
	int count = 0, a = 0, b = 0, c = 0;
	if (n == 1000) n--;
 
	while (n > 0) {
		if (!(n / 100)) {
			count++;
		}
		else {
			a = n / 100;
			b = n % 100;
			c = b % 10;
			b = b / 10;
			if (b - a == c - b) count++;
		}
		n--;
	}
	return count;
}
 
int main() {
 
	int n;
	cin >> n;
	cout << AP(n) << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: $1$부터 $N$까지 각 수를 한 번씩 검사하므로 $O(N)$이다.
• 공간 복잡도: 추가 배열 없이 판별하므로 $O(1)$이다.

마무리#

한수인지 판별할 때 1자리와 2자리 수는 무조건 조건을 만족한다.