[C++백준 1065:한수]

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

1065번: 한수

문제

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

입력

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

출력

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

 

해석

한자리, 두자리 수는 모두 한수이기 때문에 한수인지 판단은 세자리 수 부터 진행하면 된다.

첫째자리와 둘째자리의 차가 둘째자리와 셋째자리의 차와 같으면 한수로 판단할 수 있다.

 

코드

#include <iostream>
using namespace std;
 
int count(int N) {
    int fir, sec, thi;
    if (N < 100) {
        return N;
    }
    else {
        int cnt = 99;
        int tmp = N + 1;
        while (tmp--) {
            if (tmp < 100)
                break;
            fir = tmp / 100;
            sec = (tmp / 10) % 10;
            thi = tmp % 10;
            if ((fir - sec) == (sec - thi)) {
                cnt++;
            }
        }
        return cnt;
    }
}
 
int main() {
    int N;
    cin >> N;
    cout << count(N);
}

 

Memo

브루트포스 알고리즘이라는 것을 처음 들어봤다. 

(브루트포스 알고리즘 : 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 탐색하고 조건에 맞는 결과만 가져오기 때문에 100%의 정확도를 보이지만 그만큼 시간을 많이 필요로 하는 알고리즘이다.)

오래동안 고민하지 않고 풀 수 있던 문제였다.