[종만북] PI - 원주율 외우기 (자바 java)

알고리즘 문제해결전략(종만북) 스터디 메인 페이지

목차

문제 : aoj-PI

 

 

풀이

  각 테스트케이스에 대해 dp[x] 를 x번째 숫자까지 표현하기 위한 최소 난이도라 정의하자. 저 정의대로 구할수만 있다면 답은 dp[문자열 길이] 가 될 것이다.

 

  현재 문자열의 z번 문자를 보고 있다고 해보자. 이 때 dp[x]가 x번째 숫자를 표현하기 위한 최소난이도임이 확실하다면 dp[z]는, min( dp[z-3] + '이전 3개의 문자 난이도', dp[z-4] + '이전 4개의 문자 난이도', dp[z-5] + '이전 5갱의 문자 난이도') 라고 할 수 있다. 따라서 이대로 구현해주면 된다! 말한대로 이전 3개, 4개, 5개의 난이도를 계산하면서 최소값을 갱신해나가면 된다. 점수 계산은 score() 함수로 처리했다.

...
    for (int i = 3; i <= len; i++) {
        for (int cut = 2; cut <= 4; cut++) {
            if (i-cut < 0 || (i-cut-1 >= 0 && dp[i-cut-1] == INF)) continue;

            dp[i] = min(dp[i], (i-cut-1<0 ? 0 : dp[i-cut-1]) + score(i-cut, i));
        }
    }
...

private int score(int from, int to) {
    // rule 1
    for (int i = from+1; i <= to; i++) {
        if (number[i] != number[from]) break;
        if (i == to) return 1;
    }

    // rule 2
    for (int i = from+1; i <= to; i++) {
        if (number[i]-1 != number[i-1]) break;
        if (i == to) return 2;
    }
    for (int i = from+1; i <= to; i++) {
        if (number[i]+1 != number[i-1]) break;
        if (i == to) return 2;
    }

    // rule 3
    for (int i = from+2; i <= to; i++) {
        if (number[i] != number[i-2]) break;
        if (i == to) return 4;
    }

    // rule 4
    int gap = number[from+1] - number[from];
    for (int i = from+2; i <= to; i++) {
        if (number[i]-gap != number[i-1]) break;
        if (i == to) return 5;
    }

    // rule 5
    return 10;
}

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

import static java.lang.Math.min;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static final int INF = Integer.MAX_VALUE;
    int[] number;

    public static void main(String[] args) throws Exception {
        int c = Integer.parseInt(br.readLine().trim());
        while (c-->0) new Main().solution();
        System.out.print(sb);
    }

    private void solution() throws Exception {
        String str = br.readLine().trim();
        number = new int[str.length()+1];
        for (int i = 1; i <= str.length(); i++) {
            number[i] = str.charAt(i-1)-'0';
        }

        int len = str.length();
        int[] dp = new int[len+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 3; i <= len; i++) {
            for (int cut = 2; cut <= 4; cut++) {
                if (i-cut < 0 || (i-cut-1 >= 0 && dp[i-cut-1] == INF)) continue;

                dp[i] = min(dp[i], (i-cut-1<0 ? 0 : dp[i-cut-1]) + score(i-cut, i));
            }
        }

        sb.append(dp[len]).append('\n');
    }

    private int score(int from, int to) {
        // rule 1
        for (int i = from+1; i <= to; i++) {
            if (number[i] != number[from]) break;
            if (i == to) return 1;
        }

        // rule 2
        for (int i = from+1; i <= to; i++) {
            if (number[i]-1 != number[i-1]) break;
            if (i == to) return 2;
        }
        for (int i = from+1; i <= to; i++) {
            if (number[i]+1 != number[i-1]) break;
            if (i == to) return 2;
        }

        // rule 3
        for (int i = from+2; i <= to; i++) {
            if (number[i] != number[i-2]) break;
            if (i == to) return 4;
        }

        // rule 4
        int gap = number[from+1] - number[from];
        for (int i = from+2; i <= to; i++) {
            if (number[i]-gap != number[i-1]) break;
            if (i == to) return 5;
        }

        // rule 5
        return 10;
    }
}

 

 

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.