[Silver IV] 한수 - 1065

문제 링크

성능 요약

메모리: 14252 KB, 시간: 124 ms

분류

브루트포스 알고리즘, 수학

제출 일자

2024년 2월 21일 19:30:52

문제 설명

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

입력

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

출력

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

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bf.readLine());
        int x[] = new int[3];
        int xflag = 0;

        if(N < 100){
            System.out.println(N);

            return;
        }

        int k = N;

        int cnt = 99;

        for(int i=100;i<=N;i++){
            k = i;
            for(int  j = 100;j>0;j/=10){
                x[xflag++] = k/j;
                k %= j;
            }
            if(x[0] - x[1] == x[1] - x[2]){
                cnt++;
            }
            xflag = 0;
        }

        System.out.println(cnt);

    }
}

문제 해설: 우선 N의 최대 숫자가 1000이었기 때문에 시간복잡도는 신경쓰지 않았다.

100이전까지는 모두 한수이기 때문에 100이전의 숫자는 자기 자신을 출력시켜 주었고,

100이후의 숫자는 배열에 집어넣은 후 차이를 비교하여 등차수열이라면 cnt를 더해주는 것으로 간단하게 해결했다