백준(1065번) - 한수

백준(1065번) - 한수

1065번: 한수

 

문제

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

 

입력

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

 

출력

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

 

 

입출력 예제

 

등차수열 및 한수 이해하기 ( 아는 사람은 Pass )

• 등차수열에 대한 이해 : 1,3,5,7,9,⋯처럼 연속한 두 항의 차가 일정한 수열을 등차수열이라고 한다. 
• 한수 : 어떤 숫자에 대해서 각 자리수들이 등차수열을 이루는 수.
• 공차(common difference) 또는 d : 연속한 두 항에서, 뒤 항에서 앞 항을 뺀 값 =>  1,3,5,7,9... 에서 두번째 항 - 첫번째항 (3-1 = 2) 은 2(공차d)가 된다. 
• 등차수열의 식      : a(n번째) ​= a + ( n − 1 ) * d  
• 579를 식에 대입   :    9       =  5  +  (  3  − 1  )  *  2

 

설명

1.  1부터 1000사이의 숫자가 들어오는데 여기서 잠시 생각해 보면 1에서 99 까지는 모두 한수이다. ( 공차가 하나거나 없기 때문에... ) 입력받은 숫자가 100미만이면 그대로 입력한다.
2.  1000 또한 딱 봐도 한수가 아니다. 그렇다면 우리는 세자리의 숫자만 확인하면 된다.  ( 100~999까지 )
3. 등차수열의 식을 이용해서 가장 마지막에 있는 숫자가 식으로 동일하게 나온다면 한수라고 보면된다. ( 단, 숫자가 3자리 이기 때문에 가능함. )
4. 이제 입력받은 숫자 n까지 반복적으로 한수가 맞는지 검사하고 true로 나온 한수의 개수를 출력하면 된다.

 

임이의 수 579가 한수인지 등차수열의 식으로 확인해 보자.  ( 문제 에서는 주어진 숫자까지 반복해서 검증하면 된다. )

a (초항) : 5

d (공차) : 2  

 

등차수열의 식 :  a(n번째) ​=  a  +  (  n  − 1  )  *  d  

실제 대입       :     9       =  5  +  (  3  − 1  )  *  2

 

식을 대입 했을 때 true가 나오면 한수로 보면 된다. 

579는 한수가 맞다.  

 

사실 코드로 보는게 백배 더 쉽다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {  
    // 1065번 - 한수
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        n = n == 1000 ? 999 : n;         // 1000은 한수가 아니기 때문에 999로 넣어준다. ( isHanNumber는 세자리만 체크하기 떄문에... )
        int result = n > 99 ? 99 : n;    // result 는 최종 결과인데 n이 99보다 큰 경우 99까지는 한수이기 때문에 99를 넣어준다. 99이하 라면 n을 그대로 대입한다.
        for (int i = 100; i <= n; ++i) {
            if(isHanNumber(i)) result++;
        }
        System.out.println(result);
    }
 
    public static boolean isHanNumber(int checkNum) {
        int a_1 = checkNum / 100;
        int a_2 = checkNum / 10 % 10;
        int a_3 = checkNum % 10;
        // a(n번째)​ = a + (n−1) * d
        return a_3 == a_1 + (3-1) * (a_3 - a_2) ;
    }
}