[BOJ][C] 1065번 한수

안녕하세요.

오늘은 백준 1065번: 한수(링크)  문제를 풀어보려고 합니다.

 

문제

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

 

입력

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

 

출력

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

 

예제 입력

110
1
210
1000
500

 

예제 출력

99
1
105
144
119

 

제한

시간 제한: 2초

메모리 제한: 128MB

 

---

풀이

문제에서 숫자의 각 자릿수가 등차수열을 이루면 한수라고 정의를 해주었습니다.

 

따라서 숫자의 자리수에 따라 경우가 나뉘며 총 2가지로 볼 수 있습니다.

 

1. 한 자리 숫자와 두 자리 숫자

한 자리의 숫자는 한 개의 숫자만 있으므로 전부 한수인 것을 알 수 있습니다. 또한 두 자리 숫자도 모두 한수입니다.

 

그 이유는 등차수열은 연속된 두 개의 수의 차이가 일정한 것인데, 두 자리 숫자는 맨 처음 두 수의 차이만 비교하고 이 값을 비교할 다른 수들이 없기 때문입니다. 즉 두 자리 숫자는 어떠한 경우에도 증가하거나 감소하는 등차수열을 갖습니다.

 

ex) 34, 60, 99

 

따라서 현재 검사하는 숫자가 100 미만일 경우 count 에 1을 더해주면 됩니다.

 

2. 세 자리 이상 숫자

세 자리 이상의 숫자는 한수의 정의에 따라 현재 숫자를 검사해주면 됩니다.

 

먼저 등차수열의 공차를 구해주기 위해, 가장 뒷 자리 숫자 - 그 앞 자리 숫자를 해줍니다.

그리고 두 번째 숫자부터 시작해서 현재 자리 숫자 - 그 앞 자리 숫자 != 공차 이면 count에 추가를 안하고 넘어갑니다.

 

위의 과정을 1부터 N까지 반복해준 후 마지막에 count값을 출력해주면 성공입니다.

 

다만 문제에서는 네 자리 숫자인 1000은 등차수열이 아니므로 제외해주면 세 자리 숫자만 검사하기 때문에

 

(i / 100) - (i / 10 % 10) == (i / 10 % 10) - (i % 10)

 

와 같이 코드를 작성해주어도 됩니다.

 

정답

#include <stdio.h>
int hansu(int n);

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", hansu(n));
	return 0;
}

int hansu(int n)
{
	int count=0;
	for (int i = 1; i <= n; i++)
	{
		if (i < 100)
			count++;
		else if (i >= 100 && i < 1000)
		{
			if ((i / 100) - (i / 10 % 10) == (i / 10 % 10) - (i % 10))
				count++;
		}
		else
			break;
	}
	return count;
}

 

일반적인(네 자리수 이상의 숫자를 포함) 경우의 코드

 

#include <stdio.h>
int hansu(int n);

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", hansu(n));
	return 0;
}

int hansu(int n)
{
    int count=0;
    for (int i = 1; i <= n; i++)
    {
        int a = i;
        if (a < 100){
            count++;
        }
        else
        {
        	count++;
        	int r = a%10 - a/10%10;
        	a/=10;
        	while(a>=10){
        		if(a%10 - a/10%10 != r){
        			count--;
        			break;
        		}
        		a /= 10;
        	}
        }
    }
    return count;
}

---

이렇게 해서 백준 1065번 한수 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!