1065번 한수 문제

in Algorithm
1065번 한수 문제

백준 완전탐색 문제

문제 링크
본 문제는 C++17을 이용하여 해결하였다.

처음 풀어본 완전탐색 알고리즘 문제이다. 문제를 보자.

문제

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

시간 제한메모리 제한
2초128MB

입출력 예

INPUTOUTPUT
11099
11
210105
1000144

문제 해결

문제 해석

해석을 해보면 입력받은 N 이하의 자연수들 중 문제에서 정의한 한수의 개수를 세라는 것이다.
여기서 주의해야될 것은 100 미만의 1자리 자연수 혹은 2자리 자연수이다. 이 수들은 자리수가 2자리 이하기 때문에 무조건 등차수열을 이룬다.
예를 들어 98은 -1 을 등차로 가진 등차수열이라는 뜻이다.

코드

처음으로 풀어본 완전탐색 알고리즘 문제였다. 또한 알고리즘 문제를 C++로 풀어본 것도 처음이다.
내가 쓴 코드를 보자.

int N, ret=0;
vector<int> val;

void splitNum(int n){
    while(n!=0) {
        val.push_back(n%10);
        n/=10;
    }
}

int solve(int N) {
    if(N<100) return N; //기저사례 : 입력받은 수가 100 미만
    if(N == 1000) ret -= 1; // 기저사례 : 입력받은 수가 1000

    for(int i=100; i<=N; ++i) {
        splitNum(i);

        if((val[2] - val[1]) == (val[1]-val[0]))
            ret += 1;

        val.clear();
    }
    return ret+99;
}

int main() {
    cin >> N;

    cout << solve(N) << endl;
}

Hansu Problem

solve 함수를 보면 N 이 100 보다 작으면 N 그 자체를 return 하는 것을 볼 수 있다. 또한 1000일 경우 리턴값을 -1을 하는 것을 볼 수 있다. 그 이유는 solve 함수 중간에 if((val[2] - val[1]) == (val[1]-val[0])) 에서 잠정적으로 입력받은 수가 3자리 수라고 가정했기 때문이다. 만약 1000이 입력되면 (val[2] - val[1]) == (val[1]-val[0]) 이 항상 참이 되기 때문에 따로 처리한다.

splitNum 함수는 입력받은 숫자를 각 자리수로 나누는 역할을 한다. 자리수별로 나눈 숫자들은 val 벡터에 넣게된다.

마무리하며

완전탐색 문제 중에서 쉬운 편에 속한 문제이다. 하지만 C++ 을 많이 안써서 그런지 로직을 짜고 코드를 적는데 오랜 시간 걸렸다. 알고리즘 테스트 문제들을 통해서 점점 익숙해져야겠다.