백준 1065: 한수 (C++)

문제 링크: www.acmicpc.net/problem/1065

1065번: 한수

문제 설명:

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

 

문제 접근 방법:

N은 1000이하의 자연수이므로 init()함수를 통해 1~1000까지 한수인지 아닌지를 배열 hansoo에 저장해뒀다.

hansoo[i] : i가 한수이면 1, 아니면 0

한 자리 혹은 두 자리 숫자면 무조건 연속된 두 개의 수의 차이가 일정하므로 한수이다.

세 자리 이상 숫자인 경우 백의 자리, 십의 자리, 일의 자리 각 숫자를 구해서 차가 일정한지 확인하고 한수인지 아닌지를 구분했다.

 

이후 N을 입력 받으면 hansoo배열을 인덱스 1~N을 돌면서 한수 개수를 세서 출력했다.

 

#include <cstdio>

 //무식하게 풀기 : 1000이하의 한수 모두 찾아 배열에 표시

int hansoo[1001]; //1을 배열 인덱스 1에

//한수 배열 만들기 : 한수면 1, 아니면 0
void init() {
	hansoo[0] = 0;
	for (int i = 1; i < 100; i++) {
		hansoo[i] = 1;		//100이하의 자연수는 모두 한수
	}
	for (int i = 100; i < 1001; i++) {
		int a = i / 100;
		int b =i / 10 - a * 10;
		int c = i % 10;

		if ((a - b) == (b - c)) {
			hansoo[i] = 1;
		}
		else hansoo[i] = 0;
	}
}

int main() {
	int input = 0, output=0;
	scanf("%d", &input);
	init();

	for (int i = 0; i < input + 1; i++) {
		if (hansoo[i] == 1)
			output++;
	}

	printf("%d", output);
}