[Algospot] 원주율 외우기

문제 정보

문제ID

PI

출제자

JongMan

출처

연습문제

시간제한

1000ms

메모리제한

65536kb

분류

동적계획법

문제 설명

숫자열이 주어졌을 때, 해당 숫자를 세자리에서 다섯자리까지의 조각들로 나누는 최적의 방법을 찾는 문제입니다.

이 때 나누어진 숫자들이 다음과 같은 패턴을 가질 경우 난이도가 부여되며, 난이도가 가장 적은 경우가 최적의 경우가 됩니다.

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

풀이 과정

모든 경우의 수를 고려하고, 이 중 최적의 경우를 구하는 문제입니다.
이와 같은 문제의 경우 동적계획법을 이용한 풀이가 가장 접합합니다.

동적 계획법은 문제를 풀기위해 하위문제로 나누어 푼다음 이를 결합하여 최종적으로 문제를 해결해 나가는 방법입니다.

이 때, 이미 해결한 하위문제를 재활용하는 방법으로 문제를 빠르게 해결할 수 있습니다.

동적계획법을 해결하는데도 역시 재귀함수를 많이 사용하지만 꼭 재귀함수를 사용할 필요는 없으며, 여기서도 재귀함수가 아닌 일반적인 반복문을 통하여 문제를 해결할 수 있습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

먼저 문제를 해결하기 위한 경우의 수를 고려합니다.
여기서 고려해야하는 경우의 수는 기본적으로 숫자를 3자리, 4자리, 5자리로 끊는 것입니다.

수가 길어짐에 따라 이 3가지를 다양하게 사용한 많은 경우의 수가 나오지만, 어떻든 처음 혹은 끝을 보면 저 3가지 경우 중에 하나로 끝나게 됩니다.

그럼 이번 문제를 해결하기 위해 가장 마지막을 채우는 것부터 문제를 작게 쪼개서 나가도록 합니다.

예를 들어 N자리로 이루어진 숫자 열이 주어졌다고 가정을 합니다. 이를 구하는 가장 최적의 수는 다음 3가지 중에 하나로 구해질 수 있습니다.

마지막을 3자리로 했을 때의 난이도 + N-3 자리 까지 최적의 난이도.
마지막을 4자리로 했을 때의 난이도 + N-4 자리 까지 최적의 난이도.
마지막을 5자리로 했을 때의 난이도 + N-5 자리 까지 최적의 난이도.

위와 같이 계속 하위 문제로 최적의 난이도를 구한다면 이번 문제를 해결 할 수 있습니다.
이를 간단하게 코드로 표한하면 아래와 같습니다.

int bestScore(int n){
    if(n<3) return 99999; //99999를 불가능한 경우로 정의한다.
    else if(n<=5) return getScore(0, n);
    int best = 99999;
    for(i=3; i<=5 i++){
       int score = getScore(n-i, i) + bestScore(n-i);
       if(score < best){
           best = score;
       }
    }
    return best;
}

위 함수는 충분히 큰 임의의 수 99999를 계산이 불가능한 경우로 정의하였습니다.
2자릿수 이하의 입력을 받았을 경우 이를 3~5자리로 끊는 것은 불가능 하겠죠.

이제 입력받은 n 열 부터 i 자리수로 끊을 경우의 점수를 계산하는 getScore 함수만 구현하면 문제를 해결 할 수 있습니다.

하지만 여기서, 입력받은 수의 자릿수가 길어지게 될 경우 위 재귀함수의 반복호출이 커지게 되고, 이는 메모리 부하가 크며, 반복해서 재귀함수를 호출하는 것에 의해 속도가 느려질 수 있습니다.

따라서 이제 다시 위 문제를 단순 반복문으로 해결해 보겠습니다.

문제를 해결하는 기본 원리는 알았으므로, 이제 1부터 시작해 최적의 점수를 찾으며, N자리까지 반복해 나갑니다.
이를 위해 최적의 점수를 저장하고 있을 배열을 b를 준비합니다.

int bestScore(int n){
    b[0] = b[1] = 99999;
    b[2] = getScroe(0, 3);
    b[3] = getScore(0, 4);
    b[4] = getScore(0, 5);

    for(int i=5; i<n; i++){
        b[i] = 99999;
        for(int j=3; j<=5; j++){
            int scroe = b[i-j] + getScore(i-j, j);
            if(score < b[i]){
                b[i] = score;
            }
        }
    }
    return b[n-1];
}

여기서 저는 한단계 더 나아가 getScore 함수를 개선했습니다. 즉 반복해서 구하는 getScore 함수가 아닌, 현재 숫자가 위 5가지 case 중 어떠한 패턴이 몇번 반복하고 있는지를 미리 구해놓을 경우 getScore 함수를 3번이나 반복하여 호출하며 소요되는 시간을 줄일 수 있습니다.

또한 이 방법은 바로 전(1,2,4번 case), 혹은 전전(3번 case) 값만 비교하여 패턴이 몇번 반복되고 있는지만 기록하면 되어 getScore 함수보다 빠르게 점수를 구할 수 있습니다.

물론 여기에는 서로 다른 패턴이 서로 다른 횟수만큼 동시에 적용되지 않아야 적용이 가능합니다.

이 문제 같은 경우, 1번(0씩 증가하는 등차수열?)이나 2번(1씩 증가하는 등차수열) 패턴이 적용 될 경우 4번 패턴도 동시에 적용이 되지만 적용 횟수가 다를 수는 없으므로 무조건 점수가 높은 앞에 패턴이 적용된 것으로 하며, 앞에 패턴이 깨질 경우 뒤에 패턴도 같이 깨지게 됩니다.

또한 3번 패턴이 적용 될 경우, 1,2,4번 패턴은 적용 될 수 없으며, 반대의 경우 역시 마찬가지입니다.

이를 구현하기 위해 몇번 case의 패턴이 반복되고 있는지 case의 점수를 기록할 sc 변수와 패턴이 몇번 반복되고 있는지 기록할 nc 변수, 그리고 1,2,4번 case의 반복패턴 비교를 위한 d 변수를 사용합니다.

각각의 case의 패턴이 반복되고 있는지 확인하는 방법은 아래와 같습니다.

1. n[i] == n[i-1]
2. (n[i] - n[i-1]) == 1(or -1)
3. n[i] == n[i-2]
4. (n[i] - n[i-1]) == d (등차수열의 일정하게 증가하는 값.)

여기서 1, 2번은 d 값이 각각 0과 1(or -1)인 등차수열로 보고 4번이 맞는지 확인 후 d 값이 0 혹은 1(or -1)인지 확인하는 과정을 거치면 됩니다.
== 소스보기 ==

결과

#

453748

문제

PI

언어

cpp

길이

864B

수행시간

5ms

결과

정답

제출일

2016-08-06