[백.단.풀.5] 한수 (1065)

Step : <함수 사용하기>

Title : " 한수 "

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7391	3389	3027	47.423%

문제

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

입력

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

출력

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

예제 입력 

110

예제 출력 

99

이 문제는 1<= N <=1000인 N값이 주어졌을때, 1<= 한수 <=N의 개수를 구하는 것이다.

이번 문제를 이해하지 못해서 걸린 시간을 제외하고는 코드 짜는 시간은 매우 짧았다. 각 자리수마다 나올 수 있는 한수의 개수를 파악해야 한다. 길이가 1000으로 정해져 있다는 것에 주목하고, 한수의 본질을 파악한다면 비교적 쉽게 풀어낼 수 있다.
 

한수의 뜻이 너무 애매하게 적어놔서 했갈렸는데, 여기서 말하는 한수의 뜻은 "각 자리수들이 등차수열을 이루는 수"이다. 등차수열이란 각 항들이 일정한 차이를 보이는 수열이다. 예를 들면 한수는 123(공차 1), 753(공차 -2), 111(공차 0)등이 가능하다.

 즉, 123 은 각 자리수를 끊어서 보면 1, 2, 3 등차 수열이 되기 때문에 한수가 된다.

이번 문제의 핵심은 1자리수, 2자리수가 한수가 되는지를 확인하는 과정에서 나온다.
결론부터 얘기하면 1자리수, 2자리수들은 모두 한수가 된다.

1자리수 인 경우 1,2,3...,9인데 이 수들은 따로 비교할 수들이 없어 한수로 그냥 인정을 해준다.
2자리수 인 경우 12,13,14,....,58,59,....97,98,99 등이 있는데 이 수들은 구할 수 있는 공차가 1개 밖에 없다.(10의자리 - 1의 자리) 따라서 공차가 뭐가 되었던 간 한수로 인정이 된다.

이걸 알고나면 쉬워진다.

1자리 수, 2자리 수는 모두 한수가 되고, 남은 것 3자리 수만 확인하면 되기 때문이다.

즉, 3자리라는 것이 정해졌기 때문에 문제가 쉬워진다.

이번 문제를 풀 때도 DP의 개념을 이용해서 전에 수가 가지는 1~n 까지의 한수의 수를 자신이 한 수이면 +1 시키는 방법으로 1000 크기의 배열에 모두 저장해 놓고, N이 입력되면 배열의 [N]  번째 값이 답이 되기 때문에 arr[N]을 바로 출력하였다.

p.s 이번에도 틀렸습니다가 나왔는데, 또 1000일 때 3자리수를 비교하게 만든 함수를 돌아서 000만 비교하여 등차수열로 인식해서 +1 을 해버리는 예외를 처리 해주지 않았다.. 마지막에 꼭 예외처리 할 것이 있는지 확인하자!!

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
 
int N;
int  hansu[1001];
 
bool findHansu(int n)
{
    int arr[3];
 
    if (n < 100) return true;
    else {
        for (int i = 0; i < 3; i++)
        {
            int tmp = n;
            for (int j = 0; j < i; j++)
                tmp /= 10;
            arr[i] = tmp % 10;
        }
 
        if (arr[0] - arr[1] == arr[1] - arr[2]) return true;
        else return false;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i < 1000; i++)
    {
        if (findHansu(i) == true) hansu[i] = hansu[i - 1] + 1;
        else hansu[i] = hansu[i - 1];
    }
    hansu[1000] = hansu[999];
 
    printf("%d\n", hansu[N]);
 
    return 0;
}