[백준] 1065번 : 한수 - [C++]

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

1065번: 한수

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

이 번 문제에서는 주의해야 할 점이 두 가지가 있다.

 

1. 1 보다 크고 입력받은 값보다 작거나 같은 한수의 개수를 출력한다.
2. 한수는 각 자리수가 등차수열을 이루는 수를 의미한다.

 

이 두 가지만 조심하여 풀면 그리 어렵지 않게 풀 수 있을 것이다.

 

 

 

본론으로 들어가보자.

등차수열(arithmetic sequence). 즉 연속하는 두 항의 차이가 모두 일정한 수열을 의미한다.

예로들면 [ 1, 1, 1, 1, 1 ] , [ 1, 2, 3, 4, 5 ] , [ 1, 3, 5, 7 ,9 ] 등이 있다.

 

등차수열을 일반 항으로 나타낸다면 아래와 같다.

즉 두 항의 차이를 d 라고 할 때, n 번째 항은 초항과 (n-1) * d 의 합과 같다는 것이다.

 

우리가 풀 문제는 각 자리수가 등차수열을 이루고 있는지를 검사하는 문제다.

근데 잘 보면 1 ~ 1000 까지의 수 중 검사할 수는 100~1000 까지 밖에 없다.

 

생각해보자. 1 ~ 99 는 모두 등차 수열이다.

1 ~ 9 는 수가 하나 그 자체로 수열에 속한다.

 

10 ~ 99 또한 각 자리수의 차가 공차이고 그 수 자체로 수열을 이룬다.

예로들면 31 은 공차가 -2 인 수열이고, 38 은 공차가 5 인 수열이다.

 

그러면 우리가 알고리즘을 짤 때 생각해야 할 것은 100 보다 작은 수와 100 보다 큰 수의 케이스를 나누어 생각하면 되겠다.

 

 

 

그럼 하나하나씩 작성해보자.

1. 먼저 arithmetic_sequence 라는 함수와 해당 함수 안에 한수의 개수를 셀 cnt 라는 변수를 선언한다.

int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	return cnt;
}

 

이 때, 우리가 입력받은 값을 알아야지 해당 수 보다 작거나 같은 한수의 개수를 셀 것이므로 int num 을 인자로 받아들이고 한수의 개수를 나타내는 cnt 를 return 할 것이기 때문에 위와같이 구성한다.

 

 

2. 다음으로 앞서 말했듯이 1 ~ 99 의 경우 그 수 자체가 수열이라고 했다. 즉, 케이스를 num 이 100 보다 작은 경우와 큰 경우를 나눈다.

어차피 문제에서의 입력은 1 에서 1000 까지 밖에 안들어온다.

 

그리고 num 이 100 보다 작을경우는 num 을 return 해주면 된다.

즉, 86이라는 수를 입력받더라도 1 ~ 86 까지는 모두 수열이기 때문에 86개의 수열이 존재하는 것이다.

for(int i = 0; i < num; i++){
	cnt++;
}

 

이렇게 해줘도 되지만 그냥 num 을 return 해주면 굳이 반복문을 돌 필요 없이 바로 출력을 할 수가 있다.

int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
	}
    
	return cnt;
}

 

 

3. 본격적으로 else 문, 100 이상의 수들의 각 자릿수가 등차수열인지를 짜보자.

일단 100 이상의 수가 들어오면 한수의 최소 개수는 99개다. 그러므로 cnt = 99 로 초기화 해준다.

int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
		cnt = 99; 

	}
    
	return cnt;
}

 

4. 다음으로 100 부터 입력받은 값(num)까지 반복하면서 한수의 개수를 세어주어야한다.

이때 각 자릿수를 변수를 둘 것이다.

 

그리고 i 라는 정수가 있을 때 각 자릿수는 다음과 같이 구한다. 

• 백의 자릿수 = i / 100
• 십의 자릿수 = (i / 10) % 10
• 일의 자릿수 = i % 10

 

특히 십의 자릿수는 먼저 i 에 10 을 나누어서 몫을 구한 뒤 해당 몫에 10 을 나눈 나머지를 구하면 십의 자릿수가 구해진다.

예로들어 372 라는 수가 있다면 372 / 10 = 37 이 되고 여기에 %10, 즉, 37 % 10 = 7 으로 372 의 십의 자릿수를 구할 수 있다.

int arithmetic_sequence(int num){
	int cnt = 0;	// 한수 카운팅
    
	if(num < 100){
		return num;
	}
    
	else {
		cnt = 99; 
        
		for(int i = 100; i <= num; i++){
			int hun = i / 100;	// 백의 자릿수
			int ten = (i / 10) % 10;	// 십의 자릿수
			int one = i % 10;
            
			if((hun - ten) == (ten - one)){	// 각 자릿수가 수열을 이루면
				cnt++;
			}
		}
	}
    
	return cnt;
}

그리고 조건문에서 주의를 해야할 것이 등차수열이므로 각 자릿수 순서대로 차이 값을 구해야 한다.

무슨 말이냐면 135 라는 수의 각 자릿수의 공차를 구하려면 백의 자리부터 차례대로 빼거나, 일의 자리부터 차례대로 빼야한다는 것이다.

 

즉, (1-3), (3-5) 를 하거나, (5-3), (3-1) 을 하라는의미다.

 

 

이렇게 짜면 함수를 다 구현한 것이다.

 

그럼 전체 코드를 보자.

 

 

 

 

 

 

 

 

---

• 1가지 방법을 사용하여 풀이한다.

 

이 번 문제 또한 함수 중심으로 풀이하는 것이기도 하고, 빠른 입출력 방식을 사용하지 않더라도 시간은 동일하게 나온다.

그러니 별다른 거 없이 위 풀이 방식에 맞추어 한 가지 방식으로만 보여주도록 하겠다.

 

1. 기본 풀이

 

 

 

 

 

---

• 풀이

- 방법 1 : [기본 풀이]

 

#include <iostream>

using namespace std;

int arithmetic_sequence(int num) {
	int cnt = 0; // 한수 카운팅

	if (num < 100) {
		return num;
	} else {
		cnt = 99;

		for (int i = 100; i <= num; i++) {
			int hun = i / 100;		 // 백의 자릿수
			int ten = (i / 10) % 10; // 십의 자릿수
			int one = i % 10;

			if ((hun - ten) == (ten - one)) { // 각 자릿수가 수열을 이루면
				cnt++;
			}
		}
	}
	return cnt;
}

int main(int argc, char const *argv[]) {

	int N;
	cin >> N;

	int result = arithmetic_sequence(N);
	cout << result;
	return 0;
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

 

위 풀이 방법을 이해하셨다면 그리 어렵지 않게 푸실 수 있으실 것이다.

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 41873156  -  방법 1

 

 

 

---

• 정리

 

이 번 문제로 함수 부분은 끝났다. 아마 그리 어려운 점은 없었을 것이다. 

 

보통 C++ 혹은 C에서는 inline 함수라던가.. 포인터 등 많은 방식이 있긴 하지만, 일단 필자의 경우는 지금도 그렇고 앞으로도 최대한 이해하기 쉽게 하기위해 포인터를 최대한 지양하여 풀이 할 생각이다.

물론 포인터를 써야 할 때가 반드시 생기긴 하지만, 이러한 불가피한 부분을 제외하고서는 무분별하게 포인터를 쓰면 참고하려는 사람도 이해하기 난해할 때가 많아지고, 필자도 그런 방식을 그렇게 좋아하진 않으니.. 최대한 지양하는 것이 맞다고 본다.

 

(참고로 코드 스타일에 대해 문의한 것이 있는데, 왜 BSD 스타일이 아니라 K&R 스타일을 쓰냐고 하시는데, 필자도 처음에는 C++ 문제풀이를 할 때 전통적인 C 스타일, 즉 BSD스타일로 할까 하다가 막상 쓰다보니 코드 줄이 불필요하게 길어지는 것과, 일단 필자가 K&R 스타일이 편하다는 점 때문에 K&R 스타일로 하기로 했다. 덧붙여 google C++ style guide 에서는 K&R의 괄호 스타일을 따라간다. 즉, BSD가 절대적으로 옳은 것은 아니라는 점.)