문제

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

입력

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

출력

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

예제 입력/출력

코드

#include <iostream>

using namespace std;

int main() {

	int n, cnt = 99;

	scanf("%d", &n);

	// n이 100미만인 경우는 해당 수까지가 한수의 개수
	if (n < 100)
		cnt = n;
	else { // n이 100이상인 경우 100이상에 해당하는 수를 전체 탐색
		int num100, num10, num1;

		for (int i = 100; i <= n; i++) {
			num100 = i / 100; // 100의 자리 수
			num10 = (i % 100) / 10;  // 10의 자리 수
			num1 = (i % 100) % 10;  // 1의 자리 수

			// 공차가 존재하는 등비수열일 경우 한수에 해당
			if (num100 - num10 == num10 - num1 || num10 - num100 == num1 - num10)
				cnt++;
		}
	}

	printf("%d\n", cnt);

	return 0;
}

풀이1

이 문제에서 한수라는 낯선 개념을 이해하는 것이 가장 중요하다.

한수
각 자리수가 등차수열을 이루는 수.

• 한수인 수 예시
  • 1 ~ 9 : 등차수열의 길이가 1인 등차수열. eg) 1: 길이가 1인 등차수열.
  • 10 ~ 99 : 등차수열의 길이가 2인 등차수열.
    eg) 1 0 : 공차가 -1인 등차수열. / 2 4 : 공차가 +2인 등차수열. / 6 6 : 공차가 0인 등차수열.
  • 1 3 5 : 등차수열의 길이가 3이며 공차가 +2인 등차수열.
• 한수가 아닌 수 예시
  • 1 0 0 : 1에서 0으로 줄어들지만 0에서 0으로 변화가 없기 때문에 공차가 없음.
  • 1 2 4 : 1에서 2로 +1이지만 2에서 4는 +2기 때문에 공차가 없음.

위 개념을 통해서 100 미만인 모든 수들은 한수에 해당하는 것을 알 수 있다. 따라서 N이하의 수들 중에서 한수인 수의 개수를 알고 싶다면, 100이상인 수들에 대한 전체 탐색을 통해 한수의 개수를 카운트해 나가면 된다. 즉, 부르트 포스 알고리즘을 사용하면 된다.

Brute Force(브루트 포스): 무차별 대입, 일명 노가다라고도 할 수 있다. 모든 가능한 것을 하나씩 시도해보는 것이다.