👨‍💻 문제

---

✍️ 풀이

각 자리가 등차수열을 이룬다면 한수라고 한다.
자연수 N (N < 1018) 이 주어졌을 때, N보다 작은 모든 한수의 수를 구하면 된다.

완전 브루트포스

가장 쉽게 떠올릴 수 있는 방법이다.
1018개의 모든 숫자를 한수인지 확인하면 너무 오래 걸릴 것이다.
아마 시간초과 판정을 받을 것이다.

한수 구축

그렇다면 미리 한수들을 모두 뽑아놓고, N보다 작은 수만 세면 훨씬 더 빨라질 것이다.
한수를 구축하기 위해서는 자릿수 별로 반복문을 돌리고, 등차 별로 반복문을 돌리면 될 것이다.

자릿수 별 규칙

자릿수가 10자리를 넘어가면 등차는 무조건 0만 존재하게 된다.
그렇다면 그냥 10자리 이하의 등차 범위는 상수로 지정해도 무방할 듯 하다.

자릿수	가장 작은 등차를 가진 9로 시작하는 수	가장 큰 등차를 가진 1로 시작하는 수	존재 가능 등차
1	9	1	0
2	90	19	-9 ~ 8
3	951	148	-4 ~ 4
4	9630	1357	-3 ~ 2
5	97531	13579	-2 ~ 2
6	987654	123456	-1 ~ 1
7	9876543	1234567	-1 ~ 1
8	98765432	12345678	-1 ~ 1
9	987654321	123456789	-1 ~ 1
10	9876543210	1111111111	-1 ~ 0
11	99999999999	11111111111	0
12	999999999999	111111111111	0
13	9999999999999	1111111111111	0
14	99999999999999	11111111111111	0
15	999999999999999	111111111111111	0
16	9999999999999999	1111111111111111	0
17	99999999999999999	11111111111111111	0
18	999999999999999999	111111111111111111	0

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class _12347 {

    private static final int[][] possibleDiffs = {
            {0, 0},
            {0, 0}, {-9, 8}, {-4, 4}, {-3, 2}, {-2, 2},
            {-1, 1}, {-1, 1}, {-1, 1}, {-1, 1}, {-1, 0},
            {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0},
            {0, 0}, {0, 0}, {0, 0}
    };

    public static void main(String[] args) throws IOException {

        List<Long> hansoos = new ArrayList<>();
        for (int length = 1; length <= 18; length++) {
            int minDiff = possibleDiffs[length][0];
            int maxDiff = possibleDiffs[length][1];
            for (int diff = minDiff; diff <= maxDiff; diff++) {

                for (int firstValue=1; firstValue<=9; firstValue++) {
                    // 1의 자리 값이 범위 외라면 continue
                    int lastValue = firstValue+(length-1)*diff;
                    if (lastValue > 9 || lastValue < 0) {
                        continue;
                    }

                    long resultValue = 0;
                    for (int i = 0; i < length; i++) {
                        resultValue *= 10;
                        resultValue += firstValue + ((long)diff * i);
                    }
                    hansoos.add(resultValue);
                }
            }
        }
//        System.out.println(hansoos);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long N = Long.parseLong(br.readLine());
        long result = hansoos.stream().filter(value -> value <= N).count();
        System.out.println(result);

    }

}

---

💡 최적화 솔루션

존재 가능 등차를 안다면 자릿수 별로 몇 개의 한수가 존재하는지 알 수 있다.

2자리 수의 경우 아래와 같다.
9개 (11~99),
1개 (90), 2개 (91~80), 3개 (92~70), ... 9개 (98~10),
1개 (19), 2개 (18~29), 3개 (17~39), ... 8개 (12~89),

정리하면 이렇다.

자릿수	존재 가능 등차	한수의 수
1	0	9
2	-9 ~ 8	(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) + 9 + (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8)
3	-4 ~ 4	(1 + 2 + 3 + 4) + 9 + (1 + 2 + 3 + 4)
4	-3 ~ 2	(1 + 2 + 3) + 9 + (1 + 2)
5	-2 ~ 2	(1 + 2) + 9 + (1 + 2)
6	-1 ~ 1	(1) + 9 + (1)
7	-1 ~ 1	(1) + 9 + (1)
8	-1 ~ 1	(1) + 9 + (1)
9	-1 ~ 1	(1) + 9 + (1)
10	-1 ~ 0	9 + (1)
11	0	9
12	0	9
13	0	9
14	0	9
15	0	9
16	0	9
17	0	9
18	0	9

이를 활용한다면 N이 주어졌을 때, N보다 한 자리 작은 자릿수의 한수들은 굳이 만들어볼 필요 없이 계산할 수 있고,
같은 자릿수의 한수만 만들어보면 된다.