[python] algospot PI 문제풀이

문제

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

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

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

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

-> 문제 링크 : https://algospot.com/judge/problem/read/PI

algospot.com :: PI

 

문제풀이

이 문제는 부분문제로 쪼개서 풀 수 있다.

i번째 자리부터 끝까지 가는 문자열의 최소 난이도를 다음과 같이 부분 문제로 쪼갤 수 있다.

1. i+3번째 자리부터 끝까지 가는 문자열의 최소 난이도 + i ~ i+2의 난이도

2. i+4번째 자리부터 끝까지 가는 문자열의 최소 난이도 + i ~ i+3의 난이도

3. i+5번째 자리부터 끝까지 가는 문자열의 최소 난이도  + i ~ i+4의 난이도

 

i번째 자리부터 끝까지 가는 문자열의 최소 난이도는 위의 1,2,3에서 나오는 값의 최솟값에 해당한다.

기저 사례는 i가 문자열의 길이와 같아지는 순간으로 문자열의 끝까지 도달한 상황이다.

 

이를 구현하기 위해 calculate_level, pi 함수를 만들었다.

* caclulate_level(S) : 길이가 3~5인 문자열 S가 들어오면 이 문자열의 난이도를 계산해서 반환한다.

* pi(start) : start번째 자리부터 끝까지 가는 문자열의 최소 난이도를 반환한다. 함수 내에서 for문을 통해 start+3, start+4, start+5부터 시작하는 문자열의 최소 난이도를 구하는 부분 문제들로 쪼개고, start부터 시작하는 문자열의 최소난이도를 구한 뒤 반환한다.

 

최대 문자열 길이는 10000이다. 

재귀 함수에서 3개의 부분문제로 쪼개지니까 완전 탐색으로 구현시 O(3^10000)의 시간 복잡도가 나온다.

메모이제이션을 이용하면 N크기의 리스트가 생성되고, 

재귀 한번에 3번의 for문과 난이도를 계산하는 함수가 있지만 모두  상수 시간의 복잡도를 가진다. 

총 시간 복잡도는 O(N)으로 볼 수 있다.

 

코드

import sys
sys.setrecursionlimit(10**6)

def calculate_level(S) :

    # level 1 test
    if len(set(S)) == 1 :
        return 1

    # level 2 test
    prev = S[0]-1
    for val in S :
        if val - prev != 1 :
            break
        prev = val
    else :
        return 2

    prev = S[-1] - 1
    for val in reversed(S) :
        if val - prev != 1 :
            break
        prev = val
    else :
        return 2

    # level 3 test
    twos = [S[0], S[1]]
    idx = False
    for val in S :
        if twos[idx] != val :
            break
        idx = ~idx
    else :
        return 4


    # level 4 test
    diff = S[1] - S[0]
    prev = S[0] - diff
    for val in S :
        if val - prev != diff :
            break
        prev = val
    else :
        return 5

    return 10

def pi(start) :

    # if N- start <= 2 :
    #     return 0
    if N == start :
        return 0

    if dp[start] :
        return dp[start]


    ret = float('inf')
    # 만약 start 가 N-2로 들어와 남은 문자열 길이가 2이라면, if문을 통과 못해서 return 값이 INF가 될 것이고 다른 재귀 min값 비교 과정에서 사라질 것이다
    # start +i 가 N보다 크면 재귀도 돌리지 말고 N== start면 return 0을해서 끝냄 (문자열 끝까지 다 간 상황)
    for i in range(3,6) :
        if start + i <= N :
            ret = min(ret, pi(start+i) + calculate_level(nums[start:start+i]))


    dp[start] = ret

    return dp[start]

 

초기 접근 방식과 오답의 원인

algospot에서 시간 초과가 난다. 파이썬의 문제인지 코드의 문제인지 분간이 되지 않는다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.