2661 백준

문제

문제 분석

가장 먼저 생각난 방법은 DP였다. 해당 길이의 모든 경우의 수를 메모리에 저장하고 그 다음 길이에 이전에 저장한 메모리에 1,2,3을 붙여서 새로운 문자열을 만드는 방식을 택하려 했다.

그런데 메모리 초과가 났는데 생각해보면 당연한 결과였다. n = 50이고 대충만 봐도 3^50가지 경우의 수가 존재하기 때문이었다. 

처음에는 '모든 길이'가 문제인줄 알고 어차피 이전 길이의 경우의 수만 이용하므로 이전 길이의 좋은 수열만 저장했는데 문제는 이것이 아니였다. 왜냐하면 이전 길이 경우의 수만 저장한다 하더라도 모든 길이 경우의 수를 저장할 때보다 커져봐야 1개의 추가적인 문자열만 더 표현가능하기 때문이었다. (1 + 2 + 4 < 8)

때문에 DP로는 해결할 수 없다고 생각하고 재귀를 이용하여 문제를 풀었다.

호출된 문자열에 1,2,3을 추가하고 순서대로 재귀를 이용하여 계속 문자열을 붙여나갔다.

만약에 길이가 n까지 무사히 가면 1을 리턴하고 그렇지 않으면 0을 리턴하도록 했다. 길이가 k인 함수의 입장에서 봤을 때, 만약에 호출한 함수의 리턴값이 1이면 그만해도 되므로 본인도 1을 리턴하고 그렇지 않다면 나머지 경우의 수를 확인 할 것이다. 이렇게 하다보면 가장 먼저 길이가 n에 도달하는 문자열이 정답일 것이다. (1,2,3을 차례대로 붙이므로)

이렇게 하면 메모리를 저장할 필요도 없고 재귀를 통해서 풀  수 있다.

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
int n;
int now_idx = 0;
vector<string>prev_v;
string prev_s = "1";

int gen_seq(int now_length)
{
    string tmp_s = prev_s;
    for(char j='1'; j<='3'; j++)
    {
        string now_string = tmp_s + j;
        bool flag = 0;
        for(int k=1; k<= now_length/2; k++)
        {
            string str_1 = now_string.substr(now_string.length()-k ,k); // 123456 = 6
            string str_2 = now_string.substr(now_string.length()-2*k ,k); // 
            if(str_1.compare(str_2) == 0)
            {
                flag = 1;
                break;
            }
        }
        if(flag == 0)
        {
            prev_s = now_string;
            if(now_length == n)
            {
                cout << now_string;
                return 1;
            }
            if(gen_seq(now_length+1))
            {
                return 1;
            }
        }
    }
    prev_s = tmp_s;
    return 0;
}


void solution()
{
    // code
    cin >> n;
    if(n == 1)
    {
        cout << "1";
        return;
    }
    prev_v.push_back("1");
    prev_v.push_back("2");
    prev_v.push_back("3");
    gen_seq(2);
    
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

나는 전역으로 하나의 문자열을 정의하고 그것을 갱신해나가면서 함수를 진행했는데 이전 정보를 기억하기 위해서 어차피 문자열을 하나 선언해서 저장했으므로 굳이 이렇게 할 필요없이 명확하게 인자를 전달해도 괜찮았을것이다.

메모리 초과도 날 일이 없는게 가장 깊게 들어갔을 때 총 stack에 저장된 string의 메모리는 그래봐야 51*50/2이기 때문이다.

이렇게 n이 작다면 명시적으로 표현하고 더 쉽게 표현할 수 있도록 집중하자