https://www.algospot.com/judge/problem/read/PI
algospot.com :: PI
원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용
www.algospot.com
코드설명
동적계획법을 활용합니다.
먼저 재귀호출로 완전탐색을 사용하는 경우입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static String Num;
public static int[][] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
Num = st.nextToken();
answer = memorize(0);
System.out.println(answer);
}
}
//수열 N[begin ..]를 외우는 방법 중 난이도의 최소 합을 출력한다.
public static int memorize(int begin) {
//기저사례 : 수열의 끝에 도달했을 경우
if(begin == Num.length()) return 0;
// int ret = Integer.MAX_VALUE;
int ret = ((10000 / 3) + 1) * 10 ; //혹은 987654321
for(int L=3; L<=5; L++){
if(begin + L <= Num.length()) {
ret = Math.min(ret, memorize(begin + L) + classify(begin, begin + L - 1));
}
}
return ret;
}
//N[a..b] 구간의 난이도를 반환합니다.
public static int classify(int a, int b) {
//숫자조각을 가져옵니다.
String M = Num.substring(a, b + 1);
//첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
boolean isAllSame = true;
for(int i=1; i < M.length(); i++) {
if(M.charAt(0) != M.charAt(i)) {
isAllSame = false;
break;
}
}
if(isAllSame == true) 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 == true && Math.abs(M.charAt(1) - M.charAt(0)) == 1) {
return 2;
}
// 두수가 번갈아 등장하는지 확인합니다.
//첫번쨰숫자와 두번쨰 숫자, 즉 2개의 숫자만 번갈아나오면 되기에 i%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; //두수가 번갈아 등장하면 난이도는 4
if(progressive) return 5; //공차가 1 아닌 등차수열의 난이도는 5
return 10; //이 외는 모두 난이도 10
}
}이 문제의 classify 함수의 여러 조건들에 대한 처리를 올바르게 해야합니다.
또, 문제에서 처음에 ret = Integer.MAX_VALUE로 처리했었는데 범위를 벗어나서 올바른 값이 나오지 않습니다.
// int ret = Integer.MAX_VALUE; //Integer.MAX_VALUE는 오류가 납니다.
// int ret = ((10000 / 3) + 1) * 10 ; //혹은 987654321
for(int L=3; L<=5; L++){
if(begin + L <= Num.length()) {
ret = Math.min(ret, memorize(begin + L) + classify(begin, begin + L - 1));
}
}
return ret;ret에 더해지는 과정은 없고, Math.min 으로 최소값으로 변경하는 값이 반환되어 상관없다고 생각했습니다.
하지만, 만약 8자리 글이 들어왔다고 가정해봅니다. 12345678 이 들어왔다고 가정합니다. 이떄 123 456 78 이렇게 3가지 조각으로 나뉘어지는데 78의 경우 L = 3 ~ 5까지 조건이 아니면서 begin == Num.length()도 아니므로 그대로 ret을 반환합니다. 이떄, Integer.MAX_VALUE로 반환되면서 어처피 해당값은 ret의 min값이 될 수 없어야 정상이지만, 재귀함수의 구조상 456 의 classify값은 계산된뒤 더해져야 합니다. 이 과정에서 산술오버플로가 발생하면서 범위가 초과되고 -2147483638 과 같은 값이 계산되어 반환됩니다. 문제에서는 반드시 조각을 3~5조각으로 나눈다고 하였으므로 123 456 78 대신에 123 45678 과 같은 구조로 계산될 것을 예상할 수 있습니다. 만약 3~5조각으로 나눠지지 않는다면 애초에 min 값의 난이도로 계산되므로 이와 같은 구조는 제외됩니다. (이런 구조는 왜 오류가 났을까 생각해보며 알게되었습니다. )
이렇게 만약 3~5 조각으로 나눠지지 않는다면 애초에 min 과정에서 최대값으로 반환되므로 답이 될 수 없음을 알 수 있습니다. 알아서 필터링되는 것 입니다.
해결방안으로는 그렇기에 10000글자로 (10000/3 + 1) * 10 으로 최대값을 선언하거나 987654321 로 처리하면 됩니다.
-2147483638
-2147483644
-2147483647
-2147483635
두번쨰 코드는 메모이제이션을 적용하여 부분 문제에 대한 중복연산을 제거하겠습니다.
첫번쨰 코드는 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어보며 그 중 난이도의 합이 가장 작은 조합을 찾아냅니다. 각 재귀 함수는 한번 불릴떄마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼갭니다. 첫 조각의 길이는 3, 4, 5 중 하나이므로 각 경우마다 하나씩의 부분 문제를 풀어야 합니다. 이때 세개의 부분 문제에 대한 최적해를 각각 구했다고 하면, 전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이 됩니다.
1. 길이 3인 조각의 난이도 +3 글자 뺴고 나머지 수열에 대한 최적해
1. 길이 4인 조각의 난이도 +4 글자 뺴고 나머지 수열에 대한 최적해
1. 길이 5인 조각의 난이도 +5 글자 뺴고 나머지 수열에 대한 최적해
나머지 수열의 최적해를 구할때 앞의 부분을 어떤 식으로 쪼갰는지는 중요하지 않습니다. (최적 부분 구조, Optimal Substructure가 성립한다는 의미입니다.) 따라서 부분 수열의 시작 위치 begin이 주어졌을떄 최소 난이도를 반환하는 함수를 정의할 수 있습니다.
memorize(begin) = min(L=3부터 5) (memorize (begin + L) + classify(N(begin), L));
이 함수는 begin이 같을 떄 항상 같은 값을 반환하므로, 메모이제이션을 사용할 수 있습니다.
시간복잡도는 최대 n개의 부분 문가 있고, 각 부분 문제를 해결하는데 최대 세 개의 부분문제가 존재합니다. 각 부분문제를 해결하는데 걸리는 시간은 O(1)입니다.(반복문 없음) 따라서 시간복잡도는 O(n)입니다. Classify는 예외입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static String Num;
public static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
Num = st.nextToken();
cache = new int[Num.length()];
Arrays.fill(cache, -1);
answer = memorize(0);
System.out.println(answer);
}
}
//수열 N[begin ..]를 외우는 방법 중 난이도의 최소 합을 출력한다.
public static int memorize(int begin) {
//기저사례 : 수열의 끝에 도달했을 경우
if(begin == Num.length()) return 0;
if(cache[begin] != -1) return cache[begin];
cache[begin] = ((10000 / 3) + 1) * 10 ; //혹은 987654321
for(int L=3; L<=5; L++){
if(begin + L <= Num.length()) {
cache[begin] = Math.min(cache[begin], memorize(begin + L) + classify(begin, begin + L - 1));
}
}
return cache[begin];
}
//N[a..b] 구간의 난이도를 반환합니다.
public static int classify(int a, int b) {
//숫자조각을 가져옵니다.
String M = Num.substring(a, b + 1);
//첫 글자만으로 이루어진 문자열과 같으면 난이도는 1
boolean isAllSame = true;
for(int i=1; i < M.length(); i++) {
if(M.charAt(0) != M.charAt(i)) {
isAllSame = false;
break;
}
}
if(isAllSame == true) 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 == true && Math.abs(M.charAt(1) - M.charAt(0)) == 1) {
return 2;
}
// 두수가 번갈아 등장하는지 확인합니다.
//첫번쨰숫자와 두번쨰 숫자, 즉 2개의 숫자만 번갈아나오면 되기에 i%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; //두수가 번갈아 등장하면 난이도는 4
if(progressive) return 5; //공차가 1 아닌 등차수열의 난이도는 5
return 10; //이 외는 모두 난이도 10
}
}
다르게 작성해본 코드입니다. (상단의 코드보다는 비효율적)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = 0;
public static int MAX = 3334 * 10 + 1;
public static char[] arr;
public static int[] cache;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
C = Integer.parseInt(st.nextToken());
while(C-- >0) {
st = new StringTokenizer(br.readLine());
arr = st.nextToken().toCharArray();
cache = new int[arr.length + 1];
Arrays.fill(cache, -1);
System.out.println(PI(0));
}
}
//[pos..]위치에서 시작했을때의 최소 난이도 부분문제.
public static int PI(int pos) {
//기저사례 : 만약 모든 끝 단어라면, 성공.
if(pos == arr.length) {
return 0;
}
if(cache[pos] != -1) return cache[pos];
int ret = MAX;
for(int i=3; i<=5; i++) {
if(pos + i <= arr.length) {
ret = Math.min(ret, PI(pos + i) + calculate(pos, pos + i - 1));
}
}
return cache[pos] = ret;
}
// [start .. end] 까지로 계산한다.
public static int calculate(int start, int end) {
//1. 모든 숫자가 같을떄.
char top = arr[start];
boolean success = true;
for(int i=start + 1; i<=end;i++) {
if(top != arr[i]) {
success = false;
break;
}
}
if(success == true) return 1;
//2. 숫자가 1씩 단조 증가하거나 단조 감소할때
//2-1. 단조증가할떄.
success = true;
int diff = (arr[start + 1] - arr[start]);
//만약 diff가 양수라면, 단조증가테스트
//만약 diff가 음수라면, 단조감소 테스트
if(diff == 1) {
for(int i=start + 1; i <= end; i++) {
if(arr[i] - arr[i-1] != 1) {
success = false;
break;
}
}
if(success==true) return 2;
}else if(diff == -1) {
for(int i=start + 1; i <= end; i++) {
if(arr[i] - arr[i-1] != -1) {
success = false;
break;
}
}
if(success==true) return 2;
}
//3. 두개의 숫자가 번갈아가며 출현할때 (예. 323)
success = true;
for(int i=start; i + 2<=end; i+=2) {
if(arr[i] != arr[i+2]) {
success = false;
break;
}
}
for(int i=start + 1; i + 2<=end; i+=2) {
if(arr[i] != arr[i+2]) {
success = false;
break;
}
}
if(success == true) return 4;
//4. 숫자가 등차수열을 이룰때.
success = true;
int firstDiff = arr[start + 1] - arr[start];
for(int i=start; i + 1<=end;i++) {
if(firstDiff != (arr[i+1] - arr[i] )) {
success = false;
break;
}
}
if(success == true) return 5;
return 10;
}
}