한수


작성일 : 2017-01-10 18:49:31
조회수 : 1118



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


우선 X가 100보다 작은 수, 즉 2자리 이하로 이루어진 수라면 모두 등차수열이 성립함을 알 수 있습니다. 문제는 3자리 이상의 자연수일 경우, 규칙을 어떻게 찾느냐가 관건일 것입니다.


문제의 조건을 보면, N이 1000보다 작거나 같은 수입니다. 즉, N으로 1000이 주어졌을 때, 100~999 까지 등차수열이 성립하는지 확인하는데는 900*3, 1000의 4개까지해서 약 2701번의 연산으로 범위 내의 모든 수를 검사할 수 있습니다.


이렇게 문제에 대해 모든 범위 내의 값을 전부 대입하여 검사하는 것을 Brute force 기법이라고 합니다. 이 문제는, 말 그대로 brute force를 이용하여 풀면 됩니다.

#include<iostream>
using namespace std;

int main()
{
    int n,t,a,b,c,s=99;
    cin>>n;
    
    if(n<100)cout<<n;
    else
    {
        for(int i=100;i<=n;i++)
        {
            bool f=true;
            t=i;
            a=t%10,t/=10,b=t%10,t/=10,c=b-a;
            while(t)
            {
                a=b,b=t%10,t/=10;
                if(b-a!=c)
                {
                    f=false;
                    break;
                }
            }
            if(f)s++;
        }
        cout<<s;
    }
}

한수 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글