1065 한수

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

1065번: 한수

한수

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

43184

20940

18092

49.038%

문제

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

입력

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

출력

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

 

 

<풀이>

1. 한 수의 정의를 찾아본다,

 각 자리수가 등차 수열을 이루는 수는 한수 라고 문제에서 정의함.

 모든 명제의 p->q 의 관계에 ~p라면 뒤의 모든 사실은 참으로,

 한 자리 숫자는 앞에는 등차 수열이라는 해당 전제를 적용 시키지 못하므로 모두 참임을 알 수 있음, 따라서 한 자리 숫자도 모두 한수의 집합에 포함 될 수 있다.

 

2. 그렇다면 두 자리 숫자는 참인가?

 공차가 한개밖에 없는 모든 수는 한수라고 정의 될 수 있으므로 참이다.

 

따라서 숫자가 세 자리 미만, 즉 100미만의 수는 입력된 수가 모두 한수가 됨을 의미한다.

 

3. 세자리 숫자

 100 <- 각자리 공차가 1, 0 같지 않으므로 한수가 될 수 없다.

 111 <- 공차가 모두 0이므로 한수

 123 <- 공차가 모두 1이므로 한수

 

이와 같은 사실을 통해 해당 숫자의 자리수 검사를 하면 간단히 풀 수 있다.

 

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

int ans;

bool hansoo(string &str);
int main(void)
{
	int N = 0;
	cin >> N;

	if (N < 100)
	{
		cout << N << '\n';
		return 0;
	}
	string str;
	for (int i = 1; i <= N; ++i)
	{
		str = to_string(i);
		if (hansoo(str))
			ans += 1;
	}
	
	cout << ans << '\n';
	return 0;
}

bool hansoo(string &str)
{
	if (str.length() < 3)
		return true;

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

	for (int i = 0; i < str.length()-1; ++i)
	{
		 if (diff != str[i] - str[i + 1])
			return false;
	}
	return true;
}