[c++] 알고리즘 문제 해결 전략 1권 :: PI (정답 코드 x)

PI

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

문제

(주의: 이 문제는 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

 

나의 답

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

#define NULL_INT -1e9
using namespace std;

map<int, int> calMap;
string s;
int a; int b; int c; int d;

int point[4] = { 1,2,4,5 };

vector<int> answer;

void calValue(int start, int value) {
    int flag[4] = { 1,1,1,1 };
    b = 1; c = NULL_INT; d = NULL_INT;
    int tmp_flag[3] = { 1,1,1 };
    int less = s.length() - start;
    if (less < 3) {
        return;
    }
    if (less <= 5) {
        tmp_flag[0] = 0; tmp_flag[1] = 0; tmp_flag[2] = 0;
        tmp_flag[less - 3] = 1;
    }
    else {
        less = 5;
    }
    for (int i = start+1; i < start+less; i++) {
        // 결과 측정
        //
        if (flag[0]==1) {
            if (s[i] != s[i - 1])
                flag[0] = 0;
        }
        //
        if (flag[1]==1) {
            if (!(abs(s[i] - s[i - 1]) == 1 && (b == NULL_INT || b == s[i] - s[i - 1])))
                flag[1] = 0;
            else {
                b = s[i] - s[i - 1];
            }
        }
        //
        if (flag[2] == 1) {
            if (c == NULL_INT)
                c = s[i - 1] - '0';
            else if (c != s[i] - '0') {
                flag[2] = 0;
            }
            else {
                c = s[i-1] - '0';
            }
        }
        //
        if (flag[3] == 1) {
            if (d == NULL_INT) {
                d = s[i] - s[i - 1];
            }
            else if (d == s[i] - s[i - 1]) {
                flag[3] = 1;
            }
            else {
                d = s[i] - s[i - 1];
                flag[3] = 0;
            }
        }



        // 결과넣기
        if (i == start + 2 && tmp_flag[0]) {
            for (int i = 0; i < 4; i++) {
                if (flag[i]) {
                    if (calMap.find(start + 3) == calMap.end() || calMap[start + 3] > value+point[i]) {
                        calMap[start + 3] = value+point[i];
                        tmp_flag[0] = 0;
                    }
                    break;
                }
            }
            if (tmp_flag[0]) {
                if (calMap.find(start + 3) == calMap.end() || calMap[start + 3] > value + 10) {
                    calMap[start + 3] = value + 10;
                }
            }
        }
        else if (i == start + 3 && tmp_flag[1]) {
            for (int i = 0; i < 4; i++) {
                if (flag[i]) {
                    if (calMap.find(start + 4) == calMap.end() || calMap[start + 4] > value + point[i]) {
                        calMap[start + 4] = value + point[i];
                        tmp_flag[1] = 0;
                    }
                    break;
                }
            }
            if (tmp_flag[1]) {
                if (calMap.find(start + 4) == calMap.end() || calMap[start + 4] > value + 10) {
                    calMap[start + 4] = value + 10;
                }
            }
        }
        else if (i == start + 4 && tmp_flag[2]) {
            for (int i = 0; i < 4; i++) {
                if (flag[i]) {
                    if (calMap.find(start + 5) == calMap.end()|| calMap[start + 5] > value + point[i]) {
                        calMap[start + 5] = value + point[i];
                        tmp_flag[2] = 0;
                    }
                    break;
                }
            }
            if (tmp_flag[2]) {
                if (calMap.find(start + 5) == calMap.end() || calMap[start + 5] > value + 10) {
                    calMap[start + 5] = value + 10;
                }
            }
        }

    }
}

int main() {
    int C;
    cin >> C;
    cin.ignore(256, '\n');
    while (C--) {
        getline(cin, s);

        if (s[s.length()-1] == ' '){
            s.erase(s.begin() + s.length() - 1);
        }

        calValue(0,0);
        vector<int> ans;
        while (calMap.size()) {
            int size = calMap.size(); 
            map<int, int>::iterator iter;
            for (int i = 0; i<size; i++) {
                iter = calMap.begin();
                if (iter->first == s.length()) {
                    ans.push_back(iter->second);
                }
                else {
                    calValue(iter->first, iter->second);
                }
                calMap.erase(iter);
            }
        }
        sort(ans.begin(), ans.end());
        answer.push_back(ans.back());
    }
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << endl;
    }
}

위의 답은 https://pastebin.com/rhMYwAN3 이곳에 있는 테스트케이스를 진행해 봤을 때 몇가지 답에 어긋난다. 범위가 큰 곳에서만 어긋나서 정확한 이유를 찾지는 못했지만, 애초에 코딩 시 잘못된 습관을 유지하는 것이 문제인듯 하여 여기에 기재한다.

1. 메모이제이션은 주소를 받아서 하는 방법으로 쓰자

2. 재귀로 돌릴 수 있는 구조이고 스택오버플로우가 안 날 정도라면 재귀함수로 구현하자

   현재 BFS같이 queue를 이용해서 구현했는데, 이부분에서 오류가 발생했는지도 모르겠다.

3. index는 헷갈리지 않게 정돈하여 쓰자.

4. 최대한 간단하게 구현하자.

다음에 꼭 다시 풀어볼 것

 

다른 답

https://jaimemin.tistory.com/319

algospot PI

이곳의 답을 보면 정석인 것 같다.