[JAVA | 백준 1065] 한수

백준 1065번 문항 www.acmicpc.net/problem/1065

 

브루트 포스 알고리즘

브루트포스 알고리즘은 일어날 수 있는 모든 경우의 수를 고려하는 방법을 말한다. 모든 경우를 고려하므로 시간 측면에서 매우 비효율 적이다. 

출처: [간단 알고리즘] 2. 모두 다 해본다 - 브루트포스(Brute Force)

 

 

문제

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

 

입력

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

 

 

출력

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

 

 

풀이

자리수를 알아내는 메서드를 만들어 if, for문에서 한수의 개수를 출력하는데 사용한다. 

문제에서 말하는 함수는 인접 자리수의 차이가 같은지를 확인해야 한다. 한 자리수는 모두 한수이며, 두 자리수도 각 자리 수의 차는 구할 수 있지만 비교대상이 없으므로 모두 한수로 본다. 따라서 본 문제는 1,000까지의 자연수로 한정하고 있으므로 세 자리 수일 때만 그 차이를 비교하면 된다.

세 자리 수는 "백의 자리 - 십의 자리 = 십의 자리 - 일의 자리" 와 같아야 하는데 각 차이는 절대값으로 비교하므로 부호의 영향을 받지 않도록 "백의 자리 + 일의 자리 = 십의 자리*2" 의 값으로 구할 수 있다.

 

 

import java.util.Scanner;
 
public class function_1065 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int input = sc.nextInt();
        int hansu = 0;
        
        for(int i=1;i<input+1;i++) {
            if(cnt(i)<3) hansu++; 
            else if(i/100+i%10==i/10%10*2) hansu++;
        }
        System.out.println(hansu);
        sc.close();
    }
    
    public static int cnt(int x) {
        int a = 1;
        for(int j=0; x/10!=0; j++) {
            a++;    
            x=x/10;
        }
    return a;
    }    
}