[백준] 1065번 한수 - Java(자바)

오늘의 백준 문제 1065번 한수

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

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

풀이

문제를 보았을때 내가 제일 중요하게 생각하는건 당연한 말일수도 있지만 어떤 프로그램을 작성해야하는지 보는것이라고 생각한다.

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

난 이해력이 부족해서 항상 이런 문제를 보면 예시를 들어야 이해가 되는데, 처음에 이해하기 위해 1부터 10까지 숫자 중 한수를 생각해보았다.

"각 자리가 등차수열을 이룬다" 부분에서 일의자리는 십의자리가 없으니 등차수열이 아닌가? 하고 처음에 생각했는데

다시 생각해보니 1 이라는 숫자는 십진법으로 표현할때 (10^1 * 0) + (10^0 * 1) 이라서 1이라고 표현할 수 있고, 이 경우에 10의 자리 수는 0, 1의 자리수는 1이기 때문에 0. 1 등차가 1인 등차수열이라고 말 할수 있을 것이다.

따라서 1,2,3,4,5,6,7,8,9 는 한수의 조건에 만족한다.

그렇다면 10은 어떨까? 십의 자리수가 1, 일의 자리수가 0 이고 등차가 -1인 등차수열일것이다.

여기까지 생각했을때 N에서 등차수열을 구하는건 상당히 많을것이라 생각했고, 등차수열이 되지 못하는 조건에 대해 생각해보았다.

11일까? 11은 십의자리수가 1, 일의 자리수가 1이고 등차가 0인 등차수열이라고 말할 수 있다.

12,13,14 또한 십의 자리수가 1, 일의 자리수가 각각  2,3,4 이고 등차가 2,3,4인 등차수열이라고 말할 수 있다.

즉, 1부터 99까지는 모두가 등차수열이 될 수 있다.

 

분기는 100부터이다. 100은 백의자리수가 1, 십의 자리수가 0, 일의 자리수가 0이고 등차수열을 만족하지 않는다.

101 또한 마찬가지. 100이 넘는 수부터는 123, 135, 147, 158... 이런 숫자가 등차수열을 만족하는 한수가 될것이다.

 

100이 넘는 수부터 1000 아래까지, 999까지일때 등차수열인지 확인하는 알고리즘을 짠다면 이 문제가 풀린다.

N의 범위는 1<= N <=1000 이라고 정해졌고, 1000은 위의 한수 조건에 만족하지 않으므로 판별하지 않았다.

N이 세자리 수일때 몫 계산과 나머지 계산을 이용하여 백의자리수, 십의자리수, 일의자리수 를 구해 각각 h, t, o 라는 변수에 저장해주었다.

(백의자리수 - 십의자리수) 와 (십의자리수 - 일의자리수) 가 같다면 등차가 같으므로 등차수열을 이루는 한수가 되고, 이 경우 answer라는 변수를 카운팅하여 최종적으로 한수의 개수를 구했다.

 

코드는 다음과 같다.

 

 

 

 

 

 

누가 볼지 모르겠지만, 풀이만 보고 코드를 보기 싫은 사람을 위해 공백을 좀 두고 아래에 코드를 쓰겠다. 혹시 여기까지 보고 직접 짜보고 싶은 사람도 있을테니...(사실 내가 그렇다. 도저히 안풀리는 문제에 대해 온전한 코드보다 풀이를 먼저 보고싶어한다. 나같은 사람도 있을수 있잖아..)

 

 

 

 

 

import java.io.*;

public class Main {
    public int solution(String str) {
        int answer = 0;
        int[] d_array = new int[2];
        for (int i = 1; i <= Integer.parseInt(str); i++) {
            if(i<100)
                answer++;
            else if (i >= 100 && i < 1000) {
                int h = i / 100;
                int t = (i % 100) / 10;
                int o = (i % 100) % 10;
                if(h-t == t-o)
                    answer++;
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main t = new Main();
        System.out.println(t.solution(br.readLine()));
    }
}

 

결과는 정답이다.

처음에는 어떤 수를 넣더라도 적용이 가능한 알고리즘을 짜야하지 않나? 이건 너무 야매가 아닌가? 하는 생각에 제출을 망설였지만, 조건에서 N의 범위를 정해주었고, 코딩테스트는 주어진 문제를 푸는 것이기 때문에 상관없지않을까?

 

다른 풀이가 있다면 댓글로 남겨주시면 감사하겠습니다.