백준알고리즘 1065번 문제 풀이 & 해설

문제

​

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

​

입력

​

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

​

출력

​

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

​

해설

​

본 문제는 등차수열인데 얼핏 알기에는 5, 10, 15, 20과 같은 수열로 착오할 수 있습니다.

문제지문에 보시면, 어떤 정수 X 의 자릿수가 등차수열을 이룬다면 이라고 적혀 있지요.

여기서 자릿수란, 숫자가 1자리인지 2자리 숫자인지, 3 또는 4자리 숫자인지 말하는 것입니다.

​

1자리는 1~9까지이고 2자리 숫자는 10~99, 3자리 숫자는 100 ~ 999.

그리고 4자리 숫자는 1000 입니다. ( 조건이 1000보다 작거나 같은 자연수가 최대범위 )

​

그 기록한 4자리 숫자를 하나하나 떼어놓았을 때 연속해서 증가하는 등차수열인지를 묻는 것이지요.

​

이를 테면 123 은 등차수열입니다. 1, 2, 3 를 모두 떼어놓았을때 숫자차이가 1이지 않습니까? 357도 등차수열이지요. 간격이 2씩이니까요.

그러면 890은요? 아쉽게도 등차수열이 될 수가 없습니다. 89까지는 조건이 맞지만, 마지막은 10이 아닌 0이기 때문에 등차수열이 아니지요.

하여간 이 문제는 이런 등차수열의 자격을 갖춘 숫자의 갯수를 1 부터 입력되어지는 N 숫자까지 찾는게 목표입니다.

여기서 애매한 규칙이 하나 있습니다.

등차수열을 판단하려면 적어도 숫자가 3개가 있어야 합니다.

그런데 1자리나 2자리 숫자인 경우 어떻게 해야 할까요?

등차수열로 인정해야 할지 아닐지입니다.

이 문제에서는 예제로 주어지는 샘플 데이터와 답안에서 그 힌트가 주어집니다.

​

N의 값이 110일때, 99개의 숫자가 등차수열이라는 것이지요.

100 ~ 110까지는 등차수열이 하나도 없습니다.

그러니까 1~99까지는 비록 등차수열을 판단할 3개의 숫자가 없더라도

등차수열로 인정해주자는 것으로 보입니다.

그래서 프로그램 소스코드에서도 1~99는 모두 등차수열로 인정을 해주도록 하였습니다.

​

그 다음으로 C 언어의 특징을 모르시는 분은 이 부분이 좀 이해가 어려울수도 있습니다.

완전한 기초는 C++ 강좌에서 다루도록 하고요.

대략적인 설명을 드리자면,

​

sprintf(cols, "%d", i);

int diff = cols[1] - cols[0];

​

우선 sprintf(cols,."%d", i) 이 부분은 cols 라는 문자열에 i라는 숫자값을 문장형태로 기록합니다. 화면에 출력하는 대신 문자열 변수에 출력한다고 생각하시면 됩니다.

만약 456 를 문자열 변수에 출력했다고 칩시다.

​

그러면 문자열 변수는 문자배열이기 때문에 문자배열의 첫번째 cols[0] 에는 문자 '4'가

문자배열의 두번째 cols[1] 에는 문자 '5'가 저장됩니다.

문자 '4'의 아스키코드값은 52입니다.

그리고 문자 '5'의 아스키코드값은 53입니다.

이 연산은 문자값 '5' ( 숫자값 53 ) 에서 문자값 '4' ( 52) 를 빼서 1의 차이가 나오지만,

뺄셈이기 때문에 5에서 4를 뺀 것과 동일한 결과가 주어집니다.

그래서 2개의 값 차이를 먼저 저장하고 3번째 문자부터 반복문을 돌려서 차이값이 일정한 것인지를 검사하는 것이 주요 포인트입니다.

​

※ 아스키코드가 궁금하시면 아래를 참조해 주세요.

 

https://itadventure.tistory.com/7

아스키 코드표

소스코드

 

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

// 자릿수 등차수열 구하기
void increment_number()
{
	int n;
	scanf("%d", &n);

	int increment_ok = 0;
	char cols[10];
	for (int i = 1; i <= n; ++i)
	{
		// 1 ~99까지는 세번째 등차수열을 탈락할 조건이 없으므로 모두 OK
		if (i < 100)
		{
			increment_ok++;
			continue;
		}
		sprintf(cols, "%d", i);

		// 첫번째 수와 두번째 수의 차이 산출
		int diff = cols[1] - cols[0];
		bool isok = true;
		int len = strlen(cols);
		// 3번째 숫자부터 판단 시작
		for (int j = 2; j < len; ++j)
		{
			// 각 자릿수마다 비교 등차수열 조건에 어긋나면
			if (cols[j] - cols[j-1] != diff)
			{
				// 탈락
				isok = false;
				// 더 검사할 필요가 없으므로 끝
				break;
			}
		}

		// 한수가 맞는 경우 OK
		if (isok)
			increment_ok++;
	}
	
	printf("%d", increment_ok);
}

int main()
{
	increment_number();
	return 0;
}

랭킹도 조금씩 올라가는군요 :)

​