BOJ 1065 한수

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

1. 문제요약

- 입력이 N일 때, 각 자릿수의 차이가 같은 수(한수)의 개수는?

※ 한 자릿수와 두 자릿수의 경우 어떻게 처리되나 했더니

예제에

입력 : 110

출력 : 99

즉, 2자리수 까지는 모두 등차수열로 판단 == 한수

2. 접근방법

n <= 1000보다 작은 자연수 이므로 세 자릿수만 한수인지 확인하면 된다.

3. 시간복잡도

- 두 자릿수 입력만 받는다면 O(1)이겠지만, 3자릿수가 넘어가면 각각의 수에 대해 확인해야하므로 O(N)

1) 각 자릿수의 차를 직접 구해보기

- 세 번째 자릿수 - 두 번째 자릿수 == 두 번째 자릿수 - 첫 번째 자릿수

소스코드

#include<iostream>
using namespace std;

int n, cnt = 0;

int main(void){
	cin >> n;
	
	for (int i = 1; i <= n; i++){
		if (i < 100)
			cnt++;
		else {
			int f = i % 10;
			int s = (i / 10) % 10;
			int t = i / 100;

			if ((f - s) == (s - t))
				cnt++;
		}
	}

	cout << cnt << "\n";
	return 0;
}

2) 등차수열의 특징을 활용

- 사실 특징이라고 할게 있나...

- a, a+d, a+2d ... 이므로 a + a+2d = (a+d) * 2

소스코드

else {
			int f = i % 10;
			int s = (i / 10) % 10;
			int t = i / 100;

			if (f+t == 2*s)
				cnt++;
		}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]