[알고스팟] 원주율 외우기 (PI)
2019. 4. 27. 12:38ㆍ카테고리 없음
문제정보
시간제한 : 1000ms
메모리 제한 : 65536kb
문제
(주의: 이 문제는 TopCoder 의 번역 문제입니다.)
가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.
이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:
모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
그 외의 경우 난이도: 10
원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.
출력
각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.
예제 입력
5
12341234
11111222
12122222
22222222
12673939
예제 출력
4
2
5
2
14
내가 푼 소스 (시간초과)
package apss;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Pi {
public static String str;
public static int dp[][];
public static final int max = 123456789;
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("/Users/projooni/sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine().trim());
for (int testCase = 1; testCase <= T; testCase++) {
str = br.readLine().trim();
dp = new int[str.length()][6];
// DP 초기화
for(int i=0; i<str.length(); i++) {
dp[i][0] = -1;
dp[i][1] = -1;
dp[i][2] = -1;
dp[i][3] = -1;
dp[i][4] = -1;
dp[i][5] = -1;
}
int result = getAllMinDifficult(0);
bw.flush();
bw.write(testCase + " " + result + "\n");
}
bw.close();
}
// 3개, 4개, 5개 패턴을 재귀호출한다.
public static int getAllMinDifficult(int idx) {
int ret = max;
ret = Math.min(ret, getMinDifficult(idx, 3));
ret = Math.min(ret, getMinDifficult(idx, 4));
ret = Math.min(ret, getMinDifficult(idx, 5));
return ret;
}
public static int getMinDifficult(int idx, int type) {
if(idx == str.length()) {
return 0;
}
// 남은 글자수 부족
if(idx > str.length()-3) {
return 10;
}
int ret = max;
for (int i = idx + type; i <= str.length(); i++) {
char ch1 = str.charAt(idx);
char ch2 = str.charAt(idx + 1);
char ch3 = 'n';
char ch4 = 'n';
char ch5 = 'n';
int diff1 = ch2 - ch1;
int diff2 = -1;
int diff3 = -1;
int diff4 = -1;
if (type >= 3) {
ch3 = str.charAt(idx + 2);
diff2 = ch3 - ch2;
}
if (type >= 4) {
ch4 = str.charAt(idx + 3);
diff3 = ch4 - ch3;
}
if (type >= 5) {
ch5 = str.charAt(idx + 4);
diff4 = ch5 - ch4;
}
if (dp[idx][type] == -1) {
dp[idx][type] = getAllMinDifficult(idx + type);
}
// 3개 패턴
if (type == 3) {
if (diff1 == 0 && diff2 == 0) {
ret = Math.min(ret, 1 + dp[idx][type]);
} else if ((diff1 == 1 && diff2 == 1) || (diff1 == -1 && diff2 == -1)) {
ret = Math.min(ret, 2 + dp[idx][type]);
} else if (diff1 + diff2 == 0) {
ret = Math.min(ret, 4 + dp[idx][type]);
} else if (diff1 == diff2) {
ret = Math.min(ret, 5 + dp[idx][type]);
} else {
ret = Math.min(ret, 10 + dp[idx][type]);
}
} else if (type == 4) {
if (diff1 == 0 && diff2 == 0 && diff3 == 0) {
ret = Math.min(ret, 1 + dp[idx][type]);
} else if ((diff1 == 1 && diff2 == 1 && diff3 == 1) || (diff1 == -1 && diff2 == -1 && diff3 == -1)) {
ret = Math.min(ret, 2 + dp[idx][type]);
} else if ((diff1 + diff2 + diff3) == diff1) {
ret = Math.min(ret, 4 + dp[idx][type]);
} else if (diff1 == diff2 && diff2 == diff3) {
ret = Math.min(ret, 5 + dp[idx][type]);
} else {
ret = Math.min(ret, 10 + dp[idx][type]);
}
} else if (type == 5) {
if (diff1 == 0 && diff2 == 0 && diff3 == 0 && diff4 == 0) {
ret = Math.min(ret, 1 + dp[idx][type]);
} else if ((diff1 == 1 && diff2 == 1 && diff3 == 1 && diff4 == 1)
|| (diff1 == -1 && diff2 == -1 && diff3 == -1 && diff4 == -1)) {
ret = Math.min(ret, 2 + dp[idx][type]);
} else if (diff1 + diff2 + diff3 + diff4 == 0) {
ret = Math.min(ret, 4 + dp[idx][type]);
} else if (diff1 == diff2 && diff2 == diff3 && diff3 == diff4) {
ret = Math.min(ret, 5 + dp[idx][type]);
} else {
ret = Math.min(ret, 10 + dp[idx][type]);
}
}
}
return ret;
}
}
알고리즘 문제해결 전략 풀이 (JAVA)
package apss;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
/*
*PI(원주율 외우기) 알고리즘 문제해결전략 풀이
* */
public class Pi_Apss_Solution {
public static String str;
public static int dp[];
public static final int max = 123456789;
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("D://sample_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine().trim());
for (int testCase = 1; testCase <= T; testCase++) {
str = br.readLine().trim();
dp = new int[str.length()];
// DP 초기화
for(int i=0; i<str.length(); i++) {
dp[i] = -1;
}
int result = memorize(0);
bw.flush();
bw.write(result + "\n");
}
bw.close();
}
public static int classify(int a, int b) {
// 숫자 조각을 가져온다.
String M = str.substring(a, b+1);
// 첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
String pat1 = "";
for(int i=0; i<M.length(); i++) {
pat1 += M.charAt(0);
}
if(pat1.equals(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;
break;
}
}
// 등차수열이고 공차가 1 혹은 -1이면 난이도는 2
if(progressive && Math.abs(M.charAt(1) - (int)M.charAt(0)) == 1) {
return 2;
}
// 두 수가 번갈아 등장하는지 확인
boolean alternating = true;
for(int i=0; i<M.length(); i++) {
if(M.charAt(i) != M.charAt(i%2)) {
alternating = false;
break;
}
}
if(alternating) return 4;
if(progressive) return 5;
return 10;
}
public static int memorize(int begin) {
// 기저 사례 : 수열의 끝에 도달했을 경우
if(begin == str.length()) {
return 0;
}
// 메모이제이션
if(dp[begin] != -1) {
return dp[begin];
}
int ret = max;
for(int L=3; L<=5; L++) {
if(begin + L <= str.length()) {
ret = Math.min(ret, memorize(begin+L) + classify(begin, begin+L-1));
}
}
dp[begin] = ret;
return ret;
}
}
회고
정규식을 제대로 세우고 접근하자..
<