[AlgoSpot] 원주율 외우기

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/PI

문제 풀이

• 동적 계획법을 이용하여 풀이하였다.
• 아래와 같은 점화식을 이용하였다.

  solve(begin) : begin부터 시작하는 문자열의 최소 난이도
  solve(begin) = min ( solve(begin + L) + validate( begin, end) )
  (3 <= L <= 5)

• 사소한 실수 때문에 정말 삽질을 많이했다..
• validate 코드를 좀 더 깔끔하게 만들 수 있다.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C;
    public static String in;
    public static int[] dp;
    public static int INF = 987654321;

    public static int validate(int s, int e) {
        boolean flag;
        char char1, char2;
        int diff;
        //1. 모든 숫자가 같을 떄 > 1
        flag = true;
        char1 = in.charAt(s);
        for (int i = s + 1; i <= e; i++) {
            if (in.charAt(i) != char1) flag = false;
        }
        if (flag) return 1;
        //3. 공차가 1인 등차수열인 경우 > 2
        flag = true;
        diff = in.charAt(s+1) - in.charAt(s);
        char1 = in.charAt(s+1);
        for (int i = s + 2; i <= e; i++) {
            if (in.charAt(i) != char1 + diff) flag = false;
            char1 = in.charAt(i);
        }
        if (flag && (diff == 1 || diff ==-1)) return 2;
        //2. 두 개의 숫자가 번갈아가며 나타날 때 > 4
        flag = true;
        char1 = in.charAt(s);
        char2 = in.charAt(s+1);
        for (int i = s; i <= e; i++) {
            if (i % 2 == s % 2 && in.charAt(i) != char1) flag = false;
            if (i % 2 == (s + 1) % 2 && in.charAt(i) != char2) flag = false;
        }
        if (flag) return 4;
        //4. 공차가 1보다 큰 등차수열인 경우 > 5 
        flag = true;
        diff = in.charAt(s+1) - in.charAt(s);
        char1 = in.charAt(s+1);
        for (int i = s + 2; i <= e; i++) {
            if (in.charAt(i) != char1 + diff) flag = false;
            char1 = in.charAt(i);
        }
        if (flag) return 5;
        //5. 나머지 > 10
        else return 10;
    }

    public static int solve(int start) {
        if (start == in.length()) return 0;
        if (dp[start] != -1) return dp[start];
        int result = INF;
        for (int i = 3; i <= 5; i++) {
            if (start + i <= in.length()) 
                result = Math.min(result, solve(start + i) + validate(start, start + i - 1));
        }
        dp[start] = result;
        return result;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        C = scanner.nextInt();
        for (int i = 0; i < C; i++) {
            in = scanner.next();  
            dp = new int[in.length()];
            for (int j = 0; j < in.length(); j++)
                dp[j] = -1;
            System.out.println(solve(0));
        }
    }
}