백준 5904 moo 게임

처음엔 문제 그대로 수열을 재귀적으로 계속 만들다가 수열의 크기가 n 이상이 되면 재귀를 끝내고 해당 수열[n]으로 문자를 찾아주는 코드를 작성했으나 역시나 메모리 초과로 실패하였다.

 

따라서 수열을 직접 구현하기보단 n자리에 위치한 문자가 m인지 o인지 자체에 집중하며 풀이했다.

수열은 세가지 조건을 합하여 만들어지는데 s(k-1) 부분 / 새로 만들어지는 부분 / s(k-1) 부분 

이 새로 만들어지는 부분에 n이 위치한다면 m인지 o인지 바로 알 수 있다. 그 이유는 n에서 s(k-1) 부분 만큼의 길이를 제거하고 난 후 n이 1이면 m 그 외의 숫자이면 o이기 때문이다. 바로 이 새로 만들어지는 부분에 n이 위치할 수 있도록 계속해서 수열을 짧게 줄여주면 된다.

 

짧게 줄이는 방법은 다음과 같다.

1. 새로 만들어지는 부분의 o를 1개 줄인다.

2. 저장해둔 이전문자열을 붙인다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int n;
int total = 3;
int midLength = 3;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    cin >> n;

    

    while(n > total) {
        total = total*2 + ++midLength;
    }

    while(true) {
        int pre = (total-midLength)/2;

        
        if(n <= pre) {
            midLength--;
            total = pre;
        } else if(n > pre + midLength) {
            n -= pre + midLength;
            midLength--;
            total = pre;
        } else {
            n -= pre;
            break;
        }
    }

    if(n == 1){
        cout << "m";
    } else{
        cout << "o";
    }
        

}