1065) 6. 함수 : 한수

문제

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

1065번: 한수

 

내 코드

한수는 쉽게 말해 123, 642, 369와 같이 등차수열과 공차의 개념이 자릿수의 숫자 간 존재하는 수를 말한다. 근데 생소한 개념이라 그런지 아니면 중요하지 않아서 그런지 백과에서 도통 찾을 수가 없었다ㅠ

한수가 뭔지 이해하고나서, '그럼 1자리 수의 경우는 어떻게 처리해?' 하는 의문에 대한 해답을 찾는데 또 시간이 걸렸다..

 

결론은 1~99 까지는 해당 수만큼 개수를 세면 되고, 100 이상부터는 별도로 계산해서 세면 된다는 것!

 

3 자릿수만 가정해서 코드를 짜면 훨씬 깔끔하지만 짜다 보니 1000인 경우에 대해서만 예외를 만드는 게 마음에 안 들어서 자릿수에 구애받지 않는 코드를 짜보았다. 테스트해보니 10,000,000 까지는 결과를 띄워주는데 역시 $O(n^2)$ 코드의 한계 때문에 그 이상은 먹통이 된다. 더 좋게 개선할 수 있을 거 같은데.. 당장은 벡터를 굳이 쓰지 않아도 되겠다는 것 정도? 아 모르겠다~~~

#include "stdio.h"
#include "vector"

int aSize(int n) {
    // 자리수 계산 함수
    int count(0);
    
    while(n != 0) {
        count++;
        n /= 10;
    }
    
    return count;
}

int d(int n) {
    // 한수 개수를 구하는 함수
    if(n < 100) return n;
    
    int count(99), size(0), temp(0);
    std::vector<int> a;
    
    for(int i(100); i <= n; i++) {
        size = aSize(i);
        a.assign(size, 0);					// 사이즈만큼 배열 크기 할당
        temp = i;
        
        for(int j(0); j < size; j++) {
            a[j] = temp % 10;					// 한자리씩 배열에다 저장
            temp /= 10;
        }
        
        temp = a[0] - a[1];
        for(int j(1); j < size; j++) {
            if(temp == (a[j] - a[j + 1])) {			// ex. 123에서 1 - 2 == 2 - 3 이면
               if((j + 1) == (size - 1)) count++;	// 최대자리수 한수 체크
               else temp = a[j] - a[j + 1];			// 다음 자리수로 이동
            }
            else break;
        }
    }
    
    return count;
}

int main() {
    int n(0);
    
    scanf("%d", &n);
    printf("%d\n", d(n));
    
    return 0;
}