[백준 1807번] 척 노리스

문제 링크: 1807번 제목

https://www.acmicpc.net/problem/1807

 

가장 먼저, K의 범위를 통해서 수를 직접 써가는 나이브한 풀이는 불가능하다는 것을 알 수 있습니다.

대신 우리가 어떤 힌트를 얻을 수 있냐고 한다면, K번째 수를 바로 구하는 것은 어려운데, (가) 어떤 수 N으로 시작하는 수가 문자열에서 몇 번째에 오는지는 구해볼 만하다는 것입니다.

예를 들기 위해서 S를 직접 써보면 다음과 같습니다.

 

12203245260728921001121213214015216172180...

 

K=40일 때 답은 8이고, 그 수는 180으로서 N=18로 시작하는 수입니다. 이를 통해 N은 K보다 작거나 같다는 사실을 알 수 있습니다. 다시 말해, (나) S[K]를 구하고자 할 때, S[K]가 해당하는 수의 N은 1보다 크거나 같고 K보다 같거나 작습니다.그렇다면 우리는 (가), (나)의 사실을 이용해 parametric search를 이용해볼 수 있겠다는 생각을 떠올리게 됩니다. 이를 통해 K가 10¹⁵라고 할지라도 50회 내외로 정답을 구할 수 있습니다.

 

남은 것은 어떤 수 N으로 시작하는 수가 문자열에서 몇 번째에 오는지를 구하는 방법입니다. 생각보다 간단합니다. 위에서 예시로 든 18을 생각해보면, 앞에 일단 1부터 17까지를 반드시 써야합니다. 이 자리수를 구하는거야 어떻게든 구할 수 있을 거고요. 여기서 추가적으로 고려해야 할 것은, 4의 배수를 제외하고는 모두 끝에다가 숫자를 하나 더 붙여야 4의 배수가 된다는 것입니다. 1에다가는 2를 붙여서 12를 만들어야 하고, 14에다가는 0을 붙여서 140을 만들어야 하는 것처럼요. 숫자 하나만 해도 되는 것은, 우리는 4의 배수를 만들고자 하는데, 14 뒤에 한 자리를 더 붙여 14X를 만든다고 할 때, 이러한 수에 4의 배수는 반드시 2개 이상 존재하기 때문입니다.

그렇다면 1부터 17까지 자리수를 모두 더한 데에다가, 4의 배수가 아닌 수의 경우 한 자리씩 더 붙으니, 4의 배수가 아닌 수의 개수를 더해주면, 18 앞에 오는 문자열의 길이가 나옵니다.

 

위에서 구한 정보를 통해 parametric search를 진행하면 되는데, 여기서 고려할 것은 N으로 시작하는 수의 시작 인덱스와 끝 인덱스를 둘 다 고려해야 한다는 것입니다. 이 부분은 코드에 idx1, idx2로 작성되어 있으며 참고하면 어렵지 않게 알 수 있습니다.

 

import java.io.*;
import java.util.*;
import static java.lang.Long.parseLong;
import static java.lang.Math.pow;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            long k = parseLong(br.readLine());
            if (k == 0) break;
            sb.append(solve(k - 1)).append('\n');
        }
        System.out.print(sb);
    }

    static int solve(long k) {
        long s = 1L;
        long e = 1000000000000000L;
        while (true) {
            long m = (s + e) >> 1;

            long h = head(m);
            long l = len(m);
            long idx1 = h;
            long idx2 = h + (m % 4 == 0 ? l - 1 : l);

            if (idx1 <= k && k <= idx2) {
                if (k == idx2 && m % 4 != 0) {
                    return m % 2 == 0 ? 0 : 2;
                }
                return String.valueOf(m).charAt((int)(k - idx1)) - '0';
            } else if (idx2 < k) {
                s = m + 1;
            } else if (idx1 > k) {
                e = m - 1;
            } else {
                throw new RuntimeException();
            }
        }
    }

    static long head(long n) { // len of string ahead n
        if (n == 1) {
            return 0;
        }

        long m = (n - 1) / 4;
        return f(n - 1) + (n - 1 - m);
    }

    static long f(long n) { // sum of numbers digits of numbers in [1, n]
        long len = len(n);
        long base = (long)pow(10, len - 1);
        return g(len) + len * (n - base + 1);
    }

    static long g(long len) { // 1~9 + 10~99 + 100~999 when len=4
        long ret = 0;
        for (int i = 0; i < len - 1; i++) {
            ret += 9 * pow(10, i) * (i + 1);
        }
        return ret;
    }

    static long len(long n) {
        return String.valueOf(n).length();
    }
}