[알고스팟] 원주율 외우기

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • PI
  • 1000ms
  • 65536kb
  • 5153
  • 1552 (30%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

(주의: 이 문제는 TopCoder 의 번역 문제입니다.)

가끔 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글자 이하의 숫자로 주어집니다.

출력

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

예제 입력

5 
12341234 
11111222 
12122222 
22222222 
12673939 

예제 출력

4
2
5
2
14

어떻게 풀까?

주목해야할 부분은 3 조각 부터 5 조각만 확인한다는 사실입니다. 따라서, 해당 문제를 풀 때에는 앞에서부터 반복문을 통해서 3 자리, 4 자리, 5자리를 확인하며 가장 최소로 만들 수 있는 난이도를 저장해 가면서 배열을 만들어 나가면, 마지막에 나오는 수가 최소 원주율 난이도인 것입니다.

12341234의 경우를 예로 보겠습니다.

123의 경우에는 난이도가 1 입니다.

1234의 경우에도 난이도는 1 입니다.

12341의 경우에는 난이도가 10 입니다.

123412의 경우에는

123의 난이도 1 + 412의 난이도 10인 11이 될 것 입니다.

1234123의 경우에는 

1. '123'의 난이도 1과 '4123'의 난이도 10을 더한 11

2. '1234'의 난이도 1과 '123'의 난이도 1을 더한 2

2 가지 난이도를 얻을 수 있습니다. 이 중에 최솟값이 2이므로 '1234123'에서는 2 난이도가 최소라는 것을 알 수 있습니다.

12341234의 경우에는

1. '123'의 난이도 1과 '41234'의 난이도 10을 더한 11

2. '1234'의 난이도 1과 '1234'의 난이도 1을 더한 2

3. '12341'의 난이도 10과 '234'의 난이도 1을 더한 11

3 가지 난이도를 얻을 수 있습니다. 이 중에 최솟값이 2 이므로, 마지막에 결과값으로 얻는 난이도는 2가 되는 것입니다!

따라서, 

i 까지 올 수 있는 최소 난이도가 diffulcyt(i)라고 하고, a 부터 b 까지의 난이도를 classify(a,b)를 이용해 구할 수 있다고 한다면

점화식은 아래와 같습니다.

difficulty(i) = min( difficulty(i-2) + classify(i-2, i), difficulty(i-3) + classify(i-3,i), difficulty(i-4) + classify(i-4,i) )

difficulty는 배열에 저장하면 해당 인덱스까지 오는데 걸리는 최소 난이도 값이 저장됩니다.

그리고, 위의 점화식에 따라서 배열을 한번만 훑어보면 결국 마지막에는 최종적으로 계산되는 난이도가 저장되는 것입니다.

classify 함수에는 위 문제에 적힌 조건을 만족시킬수 있도록 난이도를 판별해주는 함수를 작성하면 됩니다!

코드

#pragma once
//원주율 외우기
//알고스팟
//https://algospot.com/judge/problem/read/PI
 
#include<cstdio>
#include<cstring>
 
char str[10001];
int dp[10001] = { 0 };
 
int min(int i1, int i2)
{
    return i1 < i2 ? i1 : i2;
}
 
int abs(int i1)
{
    return i1 > 0 ? i1 : -i1;
}
 
int PI()
{
    int t;
    scanf("%d\n", &t);
 
 
    while (t--)
    {
        scanf("%s\n", str);
 
        int len = strlen(str);
 
        for (int i = 1; i <= len; i++)
        {
            dp[i] = 987654321;
        }
 
        for (int i = 0; i < len; i++)
        {
            char c[2];
            c[i%2] = str[i];
            c[(i+1)%2] = str[i + 1];
 
            int diff = str[i + 1] - str[i];
            bool hFlag[4] = { true, true, true, true };
 
            hFlag[0] = c[0] == c[1];
            hFlag[1] = abs(diff) == 1;
 
            for (int l = 2; l < 5; l++)
            {
                if (i + l >= len) break;
                int hard;
 
                hFlag[0] &= str[i + l] == str[i + l - 1];
                hFlag[1] &= str[i + l] - str[i + l - 1] == diff;
                hFlag[2] &= str[i + l] == c[(i + l) % 2];
                hFlag[3] &= str[i + l] - str[i + l - 1] == diff;
 
                if (hFlag[0]) hard = 1;
                else if (hFlag[1])
                {
                    hard = 2;
                }
                else if (hFlag[2])
                {
                    hard = 4;
                }
                else if (hFlag[3])
                {
                    hard = 5;
                }
                else
                {
                    hard = 10;
                }
 
                dp[i + l + 1] = min(dp[i + l + 1], dp[i] + hard);
            }
        }
 
        printf("%d\n", dp[len]);
    }
    return 0;
}