[백준 5904번] Moo 게임 (C++ / dp, 재귀,분할정복)

 

아이디어

 

위 처럼 K번째 moo string에는 K-1번째 moo string이 앞뒤로 붙고 가운데에 mo...o( o의 개수는 k+2만큼 붙는)string이 추가된다.

일단 input N에 따라 적당한 K값을 구해두고 시작하기 위해 K에 따른 moo string 길이에 대한 점화식은

dp[k-1]*2 +(k+3)이다. 그래서 구해보면

이런식이 나오게 되는데, 이는 pow(10,9)까지만 했던거고 이후 제출땐 10^10까지 구해지도록 했다.

이 범위에 따라 N의 적절한 K값을 구하고 dfs로 들어간다.

dfs의 베이스 조건은 K==0일때이고, S(k=0)일때로 보면 되겠다(moo)

moo string에서 빨간 mooo... 를 기준으로 좌 / 우로 나눴다.

빨간 moo string영역일때의 첫글자라면 m을 출력하고 나머지는 o를 출력한다.

왼쪽 영역일때는 k를 하나 줄여서 다시 dfs를 시작한다.

오른쪽 영역일때는 왼쪽 영역일때와 똑같이 k-1이나, target값이 right길이만큼 줄어들어야 하므로 빼주면서 넘긴다.

 

그림으로 K=2일때의 예를 들면 아래와 같다

이 그림 반복.

C++풀이 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll N;
ll dp[10000];

void dfs(int k, ll target){
    if(k ==0)
    {
        switch(target){
            case 1:
                cout << 'm';
                break;
            case 2:
            case 3:
                cout << 'o';
                break;
        }
        return;
    }
    ////moo mooo moo에서 mooo가운데 영역의 좌 우 인덱스
    ll left = (dp[k]-(3+k))/2+1;
    ll right = (dp[k]-(3+k))/2+(3+k);
    
    if(target >= left && target <= right)
    {
        if(target ==(dp[k]-(3+k))/2+1) cout << 'm'; // 첫글자가 'm'이므로.
        else cout << 'o'; // 나머지는 'o'
    }
    // 왼쪽 moo영역 (left보다 작은영역)
    else if(target < left{
        dfs(k-1,target);
    }
    // 오른쪽 moo영역 (right보다 큰 영역)
    else {
        dfs(k-1,target-right); // target에서 right만큼 빼줘서 넘김.
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    int dpsize = 0;
    
    //k별로 moo string의 길이 구해둔 dp
    dp[0] = 3;
    for(int i = 1; ;i++)
    {
        ll tmp = dp[i-1]*2 + (3+i);
        if(tmp <= (ll)pow(10,10))
        {
            dp[i] = tmp;
        }else {
            dpsize = i;
            break;
        }
    }
     
    
    int k;
    bool flag = false; // N= 1,2,3 들어왔을 때 예외처리 하려고.
    for(int i = 0 ; i< dpsize-1 ; i++)
    {
        if(N > dp[i] && N <= dp[i+1] )
        {  
            flag = true;
            k = i+1;
            break;
        }
    }
    
    if(!flag) k = 0;
    dfs(k, N);
}