[백준] 1065 한수 c++

1065. 한수

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

1065번: 한수

 제출 수가 굉장히 높은 것으로 보아 이 문제 역시 중요한 기초문제인것 같다. 하지만 필자는 문제의 풀이를 생각해내는데 꽤 많이 고민했다. 문제에서 주어진 '한수'를 어떻게 저장하면 좋을지 고민해가며 100~999까지의 '한수'를 모두 종이에 적어보았지만 어떠한 규칙도 발견하지 못했고, 규칙이 있어도 굉장히 복잡해질 것 같았다. 때문에 입력이 주어지면 입력된 정수까지의 한수를 모두 찾아서 세어주는 방식으로 문제를 해결해 보았다.

---

 

이 문제의 입력 조건을 살펴보면 1,000보다 작거나 같은 자연수 N이다. 입력이 굉장히 작으므로 모든 경우의 수를 시도해보아도 제한시간 내에 충분히 풀 수 있다.

 

 

먼저 '한수'가 대체 무엇인지 정확하게 알 필요가 있다. 어떤 양의 정수의 각 자리가 등차수열을 이룬다면 그 수는 한수이다. 즉, 1~99까지의 수는 모두 한수이다. 때문에 100미만의 자연수가 입력으로 주어질 경우, 아무런 계산없이 해당 수를 출력해주면 된다. 왜냐하면 100미만의 수는 한수이기 떄문이다.

if (num < 100) cout << num;

그렇다면 100이상의 수는 어떻게 처리해야할까?

100이상의 자연수가 입력으로 들어오면 100부터 입력된 자연수까지의 수가 한수인지 판단해준다.

for()문을 통하여 100부터 입력받은 수까지 cnt()라는 함수를 호출하여 처리하였다.

 

cnt()함수에서는 전달받은 값을 10으로 나눈 나머지를 벡터에 저장해주었다. 그리고 그 수를 10으로 나누어주고 다시 10으로 나눈 나머지를 벡터로 저장했다.

while (num > 0) {
		v.push_back(num % 10);
		num /= 10;
	}

이 과정을 거치는 이유는 정수를 통채로 살펴보는 것이 아닌, 정수의 각 자리수의 숫자를 살펴보기 위함이다.

위 과정을 거치면, v의 첫번째 원소는 전달된 숫자의 일의 자리를 저장하고 v의 두번째 원소는 십의 자리 마지막으로 v의 세번째 원소는 백의 자리 숫자가 된다. 이를 통하여 우리는 각 자리수의 숫자를 알 수 있게되었다.

 

--> 각 자리수를 구하는 것을 응용하는 문제가 은근 많다! 기억해 놓기로하자!!

 

 

다시 '한수'에 집중해보자. 필자가 힘들게(사실은 컴퓨터가ㅎ.,ㅎ) 벡터에 저장한 각 자리의 수들이 등차수열을 이루는지 확인한다. 

어떻게??!!

if (v[2] - v[1] == v[1] - v[0]) {		
		return 1;
	}

그냥 우리 모두가 잘 아는 if문을 사용해준다. 여기서 return 값이 1인 이유는 무엇일까?

필자는 int cnt(int num){}형식의 함수를 생성하였기 때문에 반환값으로 int값을 넘겨주어야한다.

때문에 만일 num이 등차수열을 만족한다면 1을 반환하고 만족하지 못하면 0을 반환하였다. 그리고 main함수에서 반환된 값을 sum이라는 변수에 더해줌으로써 모든 한수를 셀 수 있게된다.

 

코드:

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
int cnt(int num) {
	v.clear();
	while (num > 0) {
		v.push_back(num % 10);
		num /= 10;
	}

	if (v[2] - v[1] == v[1] - v[0]) {
		
		return 1;

	}
	else return 0;

}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(); cin.tie();
	int sum = 99;
	int num;
	cin >> num;
	if (num < 100) cout << num;
	else if (num == 1000) cout << 144;
	else {
		for (int i = 100; i <= num; i++) {
			sum+=cnt(i);
		}
		cout << sum;
	}
}