백준(BAEKJOON): 한수(1065번)

한수

문제

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

입력

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

출력

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

예제 입력 1

110

예제 출력 1

99

예제 입력 2

1

예제 출력 2

1

예제 입력 3

210

예제 출력 3

105

예제 입력 4

1000

예제 출력 4

144

• 출처 문제를 번역한 사람: baekjoon

해설

한수라는 개념이 생소해서 이 개념을 이해하는 게 이 문제에서 제일 어려운 부분인 듯하다. 임의 수들이 어떤 수열을 이루는지 확인하기 위해서는 최소한 세 개 이상의 수가 있어야 한다. 따라서 X는 최소한 세 자리 정수여야 만이 등차수열인지 확인할 수 있는 것이다. 임의의 수 n이 100이어야 각 자리수 1, 0, 0이 일정하 수열을 이루는지 판단할 수 있는 것이다.

이 점과 예제 입력 1, 2와 결과 1, 2를 보면 두자리 정수인 경우에는 모두 한수로 인정되는 것을 알 수 있다. 예제 입력 1에서 110이 입력되면, 199까지 99개의 한수와 100110까지는 한수가 한 개도 없으므로 결과가 99가 된다. 예제 입력 2에서 1이 입력되었나 역시 수열을 이루는지 판단할 수 없으나 한수로 보아 1개를 출력하였다. 즉 임의 수 n이 100 미만인 경우는 그 수가 곧 한수의 개수가 되며, 100 이상인 경우에는 99개의 한수에 새롭게 한수로 판별되는 개수만 더해주면 된다. 따라서 임의 수가 100인지의 여부에 따라 한수의 개수를 반환하는 함수를 정의하였다.

int check100(int n)
{
    int count;

    if (n < 100) {
        count = n;
    } else {
        count = 99;    
    }
    return count;
}

다음으로 한수를 판별하는 것은 최소 100에서 시작하면 된다는 점이다. 그런데 100 이상에서 첫번째 한수는 111(1, 1, 1)이므로 사실 111 이상부터 한수 여부를 체크해 주는 것이 몇 번 되지 않는 루프라도 줄이는 방법이 되겠다. 이 점을 고려하여 한수인지 여부를 확인하는 함수를 아래와 같이 정의하였다.

int checkHansu(int n)
{
    int i;
    int num[3];
    for (i = 0; i < 3; ++i) {
        if (n == 1000)
        {
            return 0;
        } else  if ( n / 10 != 0 )
        {
            num[i] = n % 10;
            n = n / 10;
        } else {
            num[2] = n % 10;
        }
    }

    if (num[0] - num[1] == num[1] - num[2])
        return 1;
    else
        return 0;
}

이 두 함수를 이용하여 아래와 같이 메인 함수를 완성하였다.

소스코드: C

#include <stdio.h>
int checkHansu(int n);
int check100(int n);

int check100(int n)
{
    int count;

    if (n < 100) {
        count = n;
    } else {
        count = 99;    
    }
    return count;
}

int checkHansu(int n)
{
    int i;
    int num[3];
    for (i = 0; i < 3; ++i) {
        if (n == 1000)
        {
            return 0;
        } else  if ( n / 10 != 0 )
        {
            num[i] = n % 10;
            n = n / 10;
        } else {
            num[2] = n % 10;
        }
    }

    if (num[0] - num[1] == num[1] - num[2])
        return 1;
    else
        return 0;
}


int main(int argc, char *argv[])
{
    int input, i;
    int result;

    scanf("%d", &input);
    result = check100(input);
    for (i = 111; i <= input; ++i) {
        result += checkHansu(i);
    }

    printf("%d\n", result);

    return 0;
}