[AlgoSpot][C++/Python] 원주율 외우기

📒 문제 설명

🔖 https://www.algospot.com/judge/problem/read/PI

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

이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:

• 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1
• 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2
• 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4
• 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5
• 그 외의 경우 난이도: 10
  
  원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 3자리에서 5자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.

✍ 입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어집니다. 각 테스트 케이스는 8글자 이상 10000글자 이하의 숫자로 주어집니다.

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

---

✏️ 풀이 과정

📝 접근

• 조각은 세 칸에서 다섯 칸 사이의 크기를 가질 수 있고, 글자 크기에 따라 조각이 여러 개로 나누어질 수 있다. 완전 탐색으로 풀이하기에는 경우의 수가 너무 많으므로 메모이제이션을 적용했다.

• 같은 로직으로 풀이한 Python 코드의 경우 시간 초과가 발생하여 C++로 작성하여 제출하니 널널하게 통과되었다.

✨ 소스 코드

# 시간 초과
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def solve(pos):
    def setDifficulty(sub):
        if len(set(sub)) == 1: 
        	return 1
        elif all(sub[i] == sub[i + 1] - 1 for i in range(len(sub) - 1)): 
        	return 2
        elif all(sub[i] == sub[i + 1] + 1 for i in range(len(sub) - 1)): 
        	return 2
        elif all(sub[i] == sub[i % 2] for i in range(len(sub))): 
        	return 4
        elif all(sub[i] == sub[i + 1] - (sub[1] - sub[0]) for i in range(1, len(sub) - 1)): 
        	return 5
        else: 
        	return 10

    if pos == len(pi): 
    	return 0
        
    ans = memo[pos]
    if ans != -1: 
    	return ans
        
    ans = float('inf')
    
    for i in range(3, 6):
        if pos + i <= len(pi):
            ans = min(ans, solve(pos + i) + setDifficulty(pi[pos:pos + i]))
    memo[pos] = ans
    
    return ans

for _ in range(int(input())):
    pi = [int(digit) for digit in str(input()).rstrip()]
    memo = [-1] * len(pi)
    print(solve(0))

#include <iostream>
#include <vector>
#include <algorithm>

const int INF = 987654321;

using namespace std;

int setDifficulty(const vector<int>& pi, int start, int end) {
    vector<int> sub(pi.begin() + start, pi.begin() + end);

    int first_value = sub[0];

    bool isAllEqual = true;
    for (int i : sub) {
        if (i != first_value) {
            isAllEqual = false;
            break;
        }
    }

    if (isAllEqual) {
        return 1;
    }

    bool isIncreasing = true;
    for (int i = 0; i < sub.size() - 1; ++i) {
        if (sub[i] != sub[i + 1] - 1) {
            isIncreasing = false;
            break;
        }
    }

    if (isIncreasing) {
        return 2;
    }

    bool isDecreasing = true;
    for (int i = 0; i < sub.size() - 1; ++i) {
        if (sub[i] != sub[i + 1] + 1) {
            isDecreasing = false;
            break;
        }
    }

    if (isDecreasing) {
        return 2;
    }

    bool isAlternate = true;
    for (int i = 0; i < sub.size(); ++i) {
        if (sub[i] != sub[i % 2]) {
            isAlternate = false;
            break;
        }
    }

    if (isAlternate) {
        return 4;
    }

    bool isArithmetic = true;
    for (int i = 1; i < sub.size() - 1; ++i) {
        if (sub[i] != sub[i + 1] - (sub[1] - sub[0])) {
            isArithmetic = false;
            break;
        }
    }

    if (isArithmetic) {
        return 5;
    }

    return 10;
}

int solve(const vector<int>& pi, int pos, vector<int>& memo) {
    if (pos == pi.size()) {
        return 0;
    }

    int ans = memo[pos];
    if (ans != -1) {
        return ans;
    }

    ans = INF;
    for (int i = 3; i <= 5; ++i) {
        if (pos + i <= pi.size()) {
            ans = min(ans, solve(pi, pos + i, memo) + setDifficulty(pi, pos, pos + i));
        }
    }

    memo[pos] = ans;
    return ans;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        string input;
        cin >> input;
        vector<int> pi(input.size());
        for (int i = 0; i < input.size(); ++i) {
            pi[i] = input[i] - '0';
        }
        vector<int> memo(pi.size(), -1);
        cout << solve(pi, 0, memo) << endl;
    }

    return 0;
}