원주율 외우기 (난이도: 하)

1. 문제 설명

(1) 원주율을 몇만 자리까지 외우는 사람들이 존재합니다.

 

(2) 이들은 이 수를 외우기 위해 사용하는 방법 중 하나는 숫자를 몇 자리씩 끊어서 외우는 것입니다.

 

(3) 이때 세 자리에서 다섯자리까지 끊어서 외운다고 하였을 때, 다음과 같은 난이도가 존재합니다.

( ex) 12341234 -> {123}, {41234} 또는 {1234}, {1234} 또는 {12341}, {234} )

경우	예	난이도
모든 숫자가 같을때	333, 5555	1
숫자가 1씩 단조 증가하거나 단조 감소할 때	23456, 3210	2
두 개의 숫자가 번갈아가며 나타날 때	323, 54545	4
숫자가 등차 수열을 이룰 때	147, 8642	5
이 외의 모든 경우	17912, 331	10

 

 

(4) 원주율의 일부가 입력으로 주어지고 난이도의 합을 세 자리에서 다섯자리까지 끊어 읽을 때, 최소의 난이도를 찾는

프로그램을 작성하시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 각 줄에 각각의 테스크 케이스의 값 N(8자리 이상, 10,000자리 이하의 자연수)

출력 조건

(1) 각 테스트 케이스마다 한 줄에 최소의 난이도를 출력

 

입력 예제

5
12341234
11111222
12122222
22222222
12673939

 

출력 예제

4

2

5

2

14

 

 

 

 

3. 제약 조건

(1) 프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 수열을 더이상 쪼갤 수 없을 경우

 

 

 

 

6. 코드

public class PI {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static String N;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[10002];
            N = sc.readLine();
            sb.append(solve(0)+"\n");
        }
        System.out.println(sb);
    } 

    private static int solve(int begin) {
        // 기저사례(1): 수열을 더이상 쪼갤 수 없을 경우
        if(begin==N.length()) return 0;

        if(cache[begin] != 0) return cache[begin];

        // 초기 리턴값을 999을 잡고 분할을 시작한다.
        int ret = 999;
        for(int L=3; L<=5; L++) {
            if(begin+L <= N.length()) cache[begin] = ret = Math.min(ret, solve(begin+L) + classify(begin, begin+L));
        }
        return ret;
    }

    private static int classify(int a, int b) {
        String M = N.substring(a, b);

        // 모든 숫자가 같은지 확인하는 과정
        if(isEqual(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씩 단조 증가 또는 단조 감소한 경우
        // 난이도 2를 리턴
        if(progressive && Math.abs(M.charAt(1)-M.charAt(0))==1) return 2;

        // 두 개의 숫자가 번갈아가는 지 확인하는 과정
        boolean alternating = true;
        for(int i=0; i<M.length()-2; i++) {
            if(M.charAt(i) != M.charAt(i+2)) alternating = false;
        }

        // 두 개의 숫자가 번갈아가며 나타날 경우
        // 난이도 4를 리턴
        if(alternating) return 4;

        // 숫자가 등차 수열을 이룰 경우
        // 난이도 5를 리턴
        if(progressive) return 5;

        // 이외숫자 0리턴
        return 10;
    }

    // 모든 숫자가 같은지 확인하는 메서드
    private static boolean isEqual(String M) {
        for(int i=0; i<M.length()-1; i++) {
            if(M.charAt(i) != M.charAt(i+1)) return false;
        }
        return true;
    }
}

 

 

 

 

7. 점화식

- N(begin, L): N[begin]에서 시작하는 길이 L인 부분 문자열

 

- classify(): 해당 조각의 난이도를 반환하는 함수