algospot PI

문제 링크입니다: https://algospot.com/judge/problem/read/PI

생각보다 쉽게 알고리즘을 생각해낼 수 있었습니다.

결과적으로는 책의 내용과 거의 같지만 getRank 함수를 최적화할 때와 INF 재정의할 때를 제외하고는 책을 참고하지 않았다는 점에서 뿌듯함을 느꼈습니다.

/*

원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록

숫자들을 세 자리에서 다섯 자리까지 끊어 읽는다.

최소의 난이도를 게산하는 프로그램을 작성하시오

 

난이도

1.모든 숫자가 같을 때 ex)333, 55555

2.숫자가 1씩 단조 증가/감소할 때 ex)23456, 3210

4.두개의 숫자가 번갈아가며 나타날 때 ex)35353, 232

5.숫자가 등차 수열을 이룰 때 ex)147, 13579

10.이 외의 모든 경우

*/

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring> //memset

using namespace std;

 

const int INF = 987654321; //안일하게 9999했다가 오답이 나왔었다

int cache[10000]; //최대 100000이므로

string num;

 

//num[a..b] 구간의 난이도 반환

int getRank(int start, int end)

{

        //숫자 조각 가져옴

        string part = num.substr(start, end - start + 1);

        //첫 글자만으로 이루어진 문자열과 같으면 난이도 1

        if (part == string(part.size(), part[0]))

               return 1;

        //등차수열 여부

        bool progressive = true;

        for (int i = 0; i < part.size() - 1; i++)

               if (part[i + 1] - part[i] != part[1] - part[0])

                       progressive = false;

        //등차수열이고 공차가 1 혹은 -1이면 난이도 2

        if (progressive && abs(part[1] - part[0]) == 1)

               return 2;

        //두 수가 번갈아 등장하는지 확인

        bool alternate = true;

        for (int i = 0; i < part.size(); i++)

               if (part[i] != part[i % 2])

                       alternate = false;

        if (alternate)

               return 4; //번갈아가며 등장하는 숫자

        if (progressive)

               return 5; //등차 수열을 이루고 공차가 1 아님

        return 10; //그 외 숫자

}

 

//수열 num[idx..]을 외우는 방법 중 난이도의 최소 합 출력

int memorize(int idx)

{

        //기저 사례:수열의 끝에 도달할 경우

        if (idx == num.size())

               return 0;

        //동적계획법

        int &result = cache[idx];

        if (result != -1)

               return result;

        result = INF;

        for (int i = 3; i <= 5; i++) //길이는 3부터 5 사이

               if (idx + i <= num.size())

                       result = min(result, memorize(idx + i) + getRank(idx, idx + i - 1)); //해당 구간 난이도+memorize(idx+i)와 result 중 작은 쪽

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               memset(cache, -1, sizeof(cache));

               cin >> num;

               cout << memorize(0) << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략