[백준][C++] 1065 한수 - 실버4

문제 보기

https://www.acmicpc.net/problem/1065

1065번: 한수

 

문제                           

 

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

 

 

입력                          

 

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

 

 

출력                          

 

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

 

 

풀이방법                 

 

처음에는 DP 문제인가 싶어서 규칙을 찾으려 했었지만...

문제를 보니 1~1000으로 범위도 작고 기껏해야 3개의 자릿수를 구해서 비교하는 문제인지라

그냥 for문을 돌려 전부 비교해 보았다.. (나중에 보니 알고리즘 분류도 브루트포스로 되어있었음.)

 

우선 한 자릿 수와 두 자릿수는 자릿수의 차를 비교할 대상이 없기 때문에 무조건 한수로 친다.

	if (N <= 99)
	{
		cout << N;
		return 0;
	}

 

 

100이 넘어가는 숫자라면,

각 자릿수를 구하는 방법만 알면 되는 문제.

자릿수 a, b, c를 구하고 a-b 값과 b-c 값을 비교하여 동일하다면 카운트를 올리자.

 

if ((i % 10 - i / 10 % 10) == (i / 10 % 10 - i / 100))
{
	sum++;
}

 

10의 자릿 수를 두 번이나 구했으나 제한 시간이 2초로 넉넉해서 별 상관은 없었다.

 

N이 1000인 경우는 예외처리를 해줘야 하나 싶을 수 있으나

1000은 어차피 한수가 아니기 때문에 그냥 신경 쓰지 않기로 했다.

 

 

 

전체 코드

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;

	if (N <= 99)
	{
		cout << N;
		return 0;
	}

	int sum = 99;

	for (int i = 100; i <= N; i++)
	{
		if ((i % 10 - i / 10 % 10) == (i / 10 % 10 - i / 100))
		{
			sum++;
		}
	}

	cout << sum;

	return 0;
}