[algospot] PI

문제링크 입니다

[PI] 문제

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

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

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

입력 값은 다음과 같습니다

5
12341234
11111222
12122222
22222222
12673939

출력값은 다음과 같습니다. (사람들 데이터 추가)

4
2
5
2
14

전체 코드는 다음과 같습니다.

//
//  PI.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/21.
//

#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("pi.txt");

int cache[10001];

string S;
bool first(int start, int end){
    char fisrt_char = S[start];
    for(int index = start+1; index<= end; index++){
        if(fisrt_char!=S[index])
            return false;
    }
    return true;
}
bool second(int start, int end){
    int prev_difference = S[start+1]-S[start];
    for(int index = start+1; index< end; index++){
        int difference = S[index+1]-S[index];
        if(abs(difference) != 1 || prev_difference != difference) return false;
    }
    return true;
}
bool third(int start, int end){
    char first = S[start];
    char second = S[start+1];
    for(int index = start+2; index<= end; index++){
        if((index % 2)  == (start % 2) ){
            if (S[index] != first) return false;
        }
        else if ((index % 2)  == ((start+1) % 2) ){
            if (S[index] != second)
                return false;
        }
    }
    return true;
}
bool forth(int start, int end){
    int prev_difference = S[start+1]-S[start];
    for(int index = start+1; index< end; index++){
        int difference = S[index+1]-S[index];
        if(prev_difference != difference) return false;
    }
    return true;
}
int difficulty(int start, int end){
    // 모든 숫자가 같을때
    if(first(start, end)){
        return 1;
    }
    // 숫자가 1씩 단조 증가하거나 감소할 때
    else if(second(start, end)){
        return 2;
    }
    // 두 숫자가 번갈아가며 나타날 때
    else if (third(start, end))
        return 4;
    // 숫자가 모두 등차 수열일 때
    else if (forth(start, end))
        return 5;
    // 이 외 에브리띵
    return 10;
}

int pi(int position){
    if(position == S.size()) return 0;
    int &ret = cache[position];
    if(ret != -1) return ret;
    ret = 999999999;
    for(int i=3; i<=5; i++){
        if(position + i <=S.size() )
            ret = min(ret, pi(position + i)+ difficulty(position, position + i-1));
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        fin >> S;
        memset(cache,-1,sizeof(cache));
        cout << pi(0) << endl;
    }
    return 0;
}