원주율 외우기

풀이

완전 탐색 알고리즘

숫자를 세 자리에서 다섯 자리까지 끊어 읽을 수 있습니다. 1111222인 숫자는 {1111, 222} 혹은 {111, 1222}로 나눌 수 있습니다. 최대 만 자리 숫자까지 입력 받으므로 최소 $2^{10000/7}=2^{1428}$ 가지 경우의 난이도의 합을 비교해야 합니다.

메모이제이션의 적용

적절한 완전 탐색 알고리즘을 만들면 메모이제이션으로 이 문제를 해결할 수 있습니다. 이 문제를 푸는 완전 탐색 알고리즘은 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보며 그중 난이도의 합이 가장 작은 조합을 찾아냅니다. 각 재귀 함수는 한 번 불릴 때마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼갭니다. 첫 조각의 길이는 3, 4, 5 중의 하나이므로 각 경우마다 하나씩의 부분 문제를 풀어야 합니다. 이때 세 개의 부분 문제에 대한 최적해를 각각 구했다고 하면, 전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이 됩니다.

• 길이 3인 조각의 난이도 + 3글자 빼고 나머지 수열에 대한 최적해
• 길이 4인 조각의 난이도 + 4글자 빼고 나머지 수열에 대한 최적해
• 길이 5인 조각의 난이도 + 5글자 빼고 나머지 수열에 대한 최적해

나머지 수열의 최적해를 구할 때 앞의 부분을 어떤 식으로 쪼갰는지는 중요하지 않습니다. (최적 부분 구조가 성립한다는 뜻입니다.) 따라서 부분 수열의 시작 위치 $begin$이 주어졌을 때 최소 난이도를 반환하는 함수 $memorize()$를 다음과 같이 정의할 수 있습니다.

$memorize(begin)=min_{L=3}^5(memorize(begin+L)+classify(N_{begin,L}))$

여기서 $N_{begin,L}$은 $N[begin]$에서 시작하는 길이 $L$인 부분 문자열이고, $classify()$는 해당 조각의 난이도를 반환하는 함수라고 합시다. 이 함수는 $begin$이 같을 때 항상 같은 값을 반환하므로, 메모이제이션으로 쉽게 최적화할 수 있습니다.

시간 복잡도 분석

위 알고리즘은 최대 $n$개의 부분 문제가 있고, 각 부분 문제를 해결하는 데 최대 세 개의 부분 문제를 봅니다. 따라서 시간 복잡도는 $O(n)$이 됩니다.

구현

import java.util.*;

public class Main {

    // 외워야할 숫자
    public static String N;
    // 캐시
    public static int[] cache;
    // 답
    public static int result;

    public static void input(Scanner scanner) {
        N = scanner.next();
        cache = new int[N.length()];
    }

    public static void solve() {
        result = memorize(0);
    }

    // 수열 N[begin..]를 외우는 방법 중 난이도의 최소 합을 반환하는 메소드
    public static int memorize(int begin) {
        // 기저 사례: 수열의 끝에 도달했을 경우
        if (begin == N.length()) return 0;
        // 메모이제이션
        if (cache[begin] != 0) return cache[begin];
        cache[begin] = 987654321;
        for(int L = 3; L <= 5; L++) {
            if (begin + L <= N.length())
                cache[begin] = Math.min(cache[begin], memorize(begin + L) + classify(begin, begin + L));
        }
        return cache[begin];
    }

    // N[a..b] 구간의 난이도를 반환하는 메소드
    public static int classify(int a, int b) {
        // 숫자 조각을 가져온다.
        String M = N.substring(a, b);
        // 첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
        if (equalAllChar(M)) return 1;
        // 등차수열인지 검사한다.
        boolean progressive = true;
        for (int i = 0; i < M.length() - 1; i++) {
            if (M.charAt(i + 1) - M.charAt(i) != M.charAt(1) - M.charAt(0)){
                progressive = false;
            }
        }
        // 등차수열이고 공차가 1 혹은 -1이면 난이도는 2
        if (progressive && Math.abs(M.charAt(1) - M.charAt(0)) == 1) return 2;
        // 두 수가 번갈아 등장하는지 확인한다.
        boolean alternating = true;
        for (int i = 0; i < M.length(); i++) {
            if (M.charAt(i) != M.charAt(i % 2)) {
                alternating = false;
            }
        }
        if (alternating) return 4;  // 두 수가 번갈아 등장하면 난이도는 4
        if (progressive) return 5;  // 공차가 1 아닌 등차수열의 난이도는 5
        return 10;                  // 이 외는 모두 난이도 10
    }

    // str의 모든 문자가 같으면 true 반환하는 메소드
    public static boolean equalAllChar(String str) {
        for (int i = 1; i < str.length(); i++) {
            if (str.charAt(i - 1) != str.charAt(i)) return false;
        }
        return true;
    }

    public static void output() {
        System.out.println(result);
    }

    public static void test() {
        System.out.println(N);
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고