[BAEKJOON] 1065. 한수 - Feat. C++

| 1065. 한수

Title :

1065. 한수

Question :

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다.

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

* 등차수열 관련 설명

2021.10.29 - [수학/수학Ⅰ] - [Sequence] 등차수열(ArithmeticProgression)

[Sequence] 등차수열(ArithmeticProgression)

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

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

Example :

Input 1
110
Output 1
99

Input 2
1
Output 2
1

Input 3
210
Output 3
105

Input 4
1000

Output 4
144

Input 5
500
Output 5
119

Limited - Time 
2 Sec

Limited - Space
128 MB

전체 FlowChart :

Code :

cl_solution.hpp

#pragma once
#include<iostream>
class cl_solution
{
	private :
		bool fn_arithmetic_progression(int num);
	public :
		int fn_run(int num);
};

cl_solution.cpp

#include "cl_solution.hpp"

bool cl_solution::fn_arithmetic_progression(int num){
	int first_num=0 ,second_num = 0, old_difference =0,difference_num = 0;
	bool check=false;
	if (num < 100) {
		return true;
	}
	while (num>=10) {
		first_num = num % 10;
		second_num = (num/10) % 10;
		difference_num = first_num - second_num;
		if (check) {
			if (difference_num != old_difference)
				return false;
		}
		check = true;
		old_difference = difference_num;
		num /= 10;
	}
	return true;
}

int cl_solution::fn_run(int num){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	int i = 1, cnt = 0;
	if (num <= 1000 && num >= 0) {
		if (num < 100)
			cnt=num;
		else {
			while (i <= num) {
				if (fn_arithmetic_progression(i))
					cnt++;
				i++;
			}
		}
		return cnt;
	}
}

main.cpp

#include"cl_solution.hpp"

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	int num = 0;
	cl_solution sol;
	std::cin >> num;
	std::cout<<sol.fn_run(num);
	return 0;
}

 

코드&문제 분석 :

이 문제를 풀기 위해서는 사용자 입력 값까지 카운트하는 루프 , 한수의 판단 여부를 반환하는 함수로 크게 두가지로 볼수 있다. 

* 문제는 세자리의 수까지 받는 걸로 되어 있지만 필자는 네자리, 다섯자리 N번째 자리 까지 받아도 한수를 돌려주는 방법으로 해결하고자 하였다.

사용변수:

Type	변수명	설명
int	num	사용자 입력 값
int	i	1~num까지 카운트하는 루프를 제어하기 위해 사용
int	cnt	한수 갯수 체크
int	firtst_num	첫 번째 비교 숫자
int	second_num	두 번째 비교 숫자
int	old_difference	이전 숫자 변화량
int	difference_num	현재 숫자 변화량
bool	check	변수 초기화로 인해 비교 연산 오류를 잡기 위해 사용

 

1. 조건

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

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

문제 이해

예제 :

사용자 입력 : 100
100을 1/0/0으로 본다.
1과 0 -> -1
0과 0 -> 0
-1과 0 이 같지 않으므로 등차수열(한수) X 

사용자 입력 : 123
123을 1/2/3으로 본다.
1과 2 -> +1
2와 3 -> +1 
1과 1이 같으므로 등차수열(한수) O

 

2. 문제 해결

2.1 조건에 부합하는 값을 입력하였는가?

	if (num <= 1000 && num >= 0) {

 

2.2 사용자 입력 값은 100보다 큰가 작은가?

* 이유 : 100보다 작은 수는 무조건 한수이다.

1 -> 공차 0 한수
2 -> 공차 0 한수
.
.
.
10 -> 공차 -1 한수
11 -> 공차 0 한수
12 -> 공차 +1 한수
.
.
.
99 -> 공차 0 한수

 

필자는 100보다 작은 수가 들어오면 자기 자신이 한수의 갯수이므로 자기 자신을 리턴시켜주었다. 

		if (num < 100)
			cnt=num;
		
		return cnt;

 

100보다 큰 수가 들어오는 경우

if (num <= 1000 && num >= 0) {
		if (num < 100)
			cnt=num;
		else {
			while (i <= num) {
				if (fn_arithmetic_progression(i))
					cnt++;
				i++;
			}
		}
		return cnt;
}

한수를 판단해주는 함수를 호출

 

2.3 한수의 판단 여부를 반환하는 함수

bool cl_solution::fn_arithmetic_progression(int num){
	int first_num=0 ,second_num = 0, old_difference =0,difference_num = 0;
	bool check=false;
	if (num < 100) {
		return true;
	}
	while (num>=10) {
		first_num = num % 10;
		second_num = (num/10) % 10;
		difference_num = first_num - second_num;
		if (check) {
			if (difference_num != old_difference)
				return false;
		}
		check = true;
		old_difference = difference_num;
		num /= 10;
	}
	return true;
}

2.3.1 100보다 작은 경우는 무조건 한수

if (num < 100) {
		return true;
}

2.3.2 반복하며 비교

필자는 숫자 제한을 안두기 위하여 %를 사용하고 num을 10으로 나누어 다음 자리수 비교 하는 방식을 사용하였다.

이에 따라 마지막수는 한번더 비교할 이유가 없기때문에 10보다 작은 경우를 체크하며 반복하였다.

while (num>=10) {

2.3.3 첫 번째수와 두번째 수 비교

이에 따라 변화량을 저장하여 다음 변화량과 비교하게 된다.

first_num = num % 10;
second_num = (num/10) % 10;
difference_num = first_num - second_num;

2.3.4 이전 변화량과 현재 변화량 비교

if (check) {
	if (difference_num != old_difference)
		return false;
}

겉에 if(check) 부분은 difference_num와 old_difference 변수 초기화 과정에서 발생되는 에러를 잡기 위함이다.

없으면 비교도 하기 전에 초기화 된 값때문에 한수가 아니라고 반환하게 된다.

2.3.5 다음 데이터 비교를 위한 작업

현재 변화량을 이전 변화량으로 넣어주고 num을 10으로 나누며 다음 데이터 비교를 가능하게 해준다.

check = true;
old_difference = difference_num;
num /= 10;

 

Result :

 

Baekjoon :

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

1065번: 한수

 

Github : 

https://github.com/Anchangun/BaekJoon/tree/main/Question/BruteForce/1065.%20%ED%95%9C%EC%88%98

GitHub - Anchangun/BaekJoon