본문 바로가기
Study/알고리즘 문제해결전략(종만북)

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

by Nahwasa 2023. 4. 2.

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

목차

    문제 : 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;
        }
    }

     

     

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

    댓글