BOJ 1065번: 한수

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다

등차수열은 연속된 두 개 수의 차이가 일정한 수열을 말한다

N이 주어졌을 대, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오

 

입력

첫째 줄에 1000보다 작거나 같은 자연수 N이 주어진다

 

출력

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

 

코드

#include <iostream>
using namespace std;
 
int getHansuCount(int num){
    int count=0;
    if(num<100)
    {
        count = num;
    }
    else{
      count+=99;
      for(int i=100;i<=num;i++){
         bool isHanSu=true;
         int idx=i,diff=(idx%10);      //,나머지
         idx/=10;
         int rest=(idx%10);      //2번째 자릿수 삽입
         diff = diff-rest;   //1번째와 2번째 자릿수의 차이 삽입
         idx/=10;
         
         while(idx>0){
            if(diff!=rest-(idx%10)){
               isHanSu=false;
               break;
            }
            rest=idx%10;
            idx/=10;
         }
         if(isHanSu)
         {
            count++;
         }
      }
    }
    return count;
}
 
 
int main() {
   int num,count=0;
   scanf("%d",&num);
   count = getHansuCount(num);
   printf("%d",count);
   return 0;
}

*간단한 해설*

한수라는 용어 자체가 너무 이해가 안되서 헤매게 된 문제이다

한수는 예를 들자면 1자리 수인 1은 한 개 밖에 없기 때문에 무조건 한수이다(등차수열을 비교할 대상이 없기 때문)

2자리 수인 10,11,12 같은 경우 (1,0) (1,1) (1,2) 이렇게 나누어 진다

등차수열은 각각 -1,0,1 로 되고 무조건 한수이다(비교할 대상이 없기 때문)

그래서 3자리 수 이하는 모두 다 한수이기 때문에 12번줄에 보면 100부터 for문이 시작된다

while문이 돌 동안 123의 경우 123%10=3 (일의 자릿수 구하기) 그 다음 123/10=12 을 한 후 12%10=2(십의 자릿수)

이런식으로 반복하여 각 자릿수를 구한다

자릿수를 구한 다음 그 전에 구한 자릿수를 빼주어 등차수열의 증감값을 구하고 그 값이 끝날때까지 동일하다면

isHanSu=true로 유지한다

 

*메모리*

1984KB

*시간*

0ms

*언어*

C++14

*코드길이*

777B

 

 

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*