원주율 외우기 (알고스팟) (PI) [JAVA]

 

문제 링크 : algospot.com/judge/problem/read/PI

algospot.com :: PI

문제 ID	시간 제한	메모리 제한	제출	정답	정답 비율
PI	1000ms	65536kb	8011	2484	31%

가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

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

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

출력

각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.

 

풀이

한 위치의 인덱스에서 가질수 있는 값은 3가지이다.

3개를 묶었을때, 4개를 묶었을때 5개를 묶었을때.

즉 3개전 지점 값 + 3개 묶은 난이도

4개전 시점 값 + 4개 묶은 난이도

5개전 시점 값 + 5개 묶은 난이도 이렇게 3가지 경우의 수 중 최소를 더해주면 된다.

식으로 표현하면 $B_{n-a} = A_{n-a-1} + level(n-a : n)$ 일때

$An = Min (B_{n-3},B_{n-4},B_{n-5})$ 로 표현할 수 있다.

그리고 이 $An$ 들을 1차원 배열에 순서대로 저장해놓으면 동적계획법으로 할 수 있다.

우선 난이도 검사 함수를 보자

start는 n-a, last는 n에 해당하고, length는 start부터 last까지 원소의 개수이다.

난이도 1 검사

pi[start] != pi[start+index]로 만약 원소가 다르면 for문을 탈출한다.

이후 index = lenghth이면 for문을 끝까지 마쳤다는 뜻으로 난이도가 1임을 알 수 있다.

난이도 2와 5는 동시에 검사한다.

바로 앞의 인덱스를 빼준 값을 flag로 놓고, 계속해서 1개씩 빼면서 flag인지 확인한다.

끝까지 완료했을때 절대값이 1이면 난이도 2, 1이아니면 난이도 5이다.

난이도 4는 2개 앞에 원소랑 같으면 4를 반복시킨다.

이때 난이도 4와 5의 검사순서가 달라도 상관이 없다. 왜냐하면 4와 5는 동시에 성립할 수 없기 때문이다.

그렇다면 문제를 풀어보자

우선 level 배열에 각 인덱스까지일때의 최소값을 저장하는데, 인덱스가 0과 1일때는 절대 성립할 수 없으므로 아무 큰 값을 넣는다.

인덱스가 2(3개),3(4개),4(5개)일때의 값들을 일일히 저장해 놓은다음.

인덱스 5부터 배열의 끝가지 각각 위의 식의 $An$에 해당하는 값들을 지속적으로 구해 갱신하면

마지막 배열의 인덱스에 최소값이 저장되게 된다.

 

코드

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static int[] pi;
    public static int[] level;
    public static void main(String[] args)throws Exception {
    	int C = Integer.parseInt(br.readLine().trim());
    	for(;C>0; C--) {
    		String s = br.readLine().trim();
    		pi = new int[s.length()];
    		level = new int[s.length()];
    		
    		int i=0;	
    		for(char c : s.toCharArray()){
    			pi[i] = Integer.valueOf(c) - 48;
    			level[i++] = 99999;
    		}
    		path();
    		sb.append(level[pi.length-1]).append("\n");
    	}
    	System.out.println(sb.toString());
    }
    
    //난이도 검사 함수
    public static int Getlev(int start, int last) {
    	
    	int length = last-start+1;
    	int index =0;
    	
    	//난이도 1 검사
    	for(index = 1; index<length; index++) {
    		if(pi[start] != pi[start+index]) break;
    	}
    	
    	if(index == length) {return 1;}
    	index = 0; //인덱스 초기화
    	
    	//난이도 2,5 검사
    	int flag = pi[start] - pi[start+1];
    	for(index = 1; index<length-1; index++) {
    		if(pi[start+index] - pi[start+index+1] != flag) break;
    	}
    	
    	if(index == length-1) {
    		if(Math.abs(flag) == 1) return 2;
    		else return 5;
    	}
    	index =0;
    	
    	//난이도 4 검사
    	for(index =0; index<length-2; index++) {
    		if(pi[start+index] != pi[start+index+2]) break;
    	}
    	if(index == length-2) {
    		return 4;
    	}
    	return 10;	
    }
    
    public static void path() {
    	//0,1은 못세게
    	level[0] = 98765; level[1] = 98765;
    	
    	//3 4 5 채워넣기
    	level[2] = Getlev(0, 2);
    	level[3] = Getlev(0, 3);
    	level[4] = Getlev(0, 4);
    	
    	for(int i=5; i< pi.length; i++) {
    		int seq3 = level[i-3] + Getlev(i-2, i); 
    		int seq4 = level[i-4] + Getlev(i-3, i);
    		int seq5 = level[i-5] + Getlev(i-4, i);
    		
    		int min = Math.min(seq3, seq4);
    		level[i] = Math.min(seq5, min);
    	}
    }
}

 

결과