[5904]Moo 게임 - c++

여러번의 시도 끝에...

---

첫 번째 아이디어

일단 기본적인 재귀 형태로 풀려고 시도했다.

당연히 안될 걸 알고 있었지만 일단 시도 했으며 결과는 당연히 메모리 초과

CODE

//Moo 게임
#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
//횟수 
int n;
int tot = 0;
bool isFine = false;

void isMoo(bool m2o){
  //true = m, false = o
  if(m2o && tot == n){
    cout << "m";
    isFine = true;
  }
  else if(!m2o && tot == n){
    cout << "o";
    isFine = true;
  }
}

void moo(int x){
  if(x == 0){
    tot+=1;
    isMoo(true);
    tot+=2;
    isMoo(false);
    return;
  }
  if(isFine)return;
  moo(x-1);
  if(isFine)return;
  tot+=1;
  isMoo(true);
  tot += x+2;
  isMoo(false);
  if(isFine)return;
  moo(x-1);
  if(isFine)return;
}

int main(){
  init();
  cin >> n;
  moo(n/2);
  return 0;
}

이렇게 해본 후 문제점이 뭔지를 찾아 나갔다.

1. 재귀를 몇번 반복해야 하는 가를 알려줘야 한다.

2. 그저 재귀만 사용해서는 풀지 못한다. (Input이 1 <= n <= 10^9) 

위의 코드에 10^9승이란 Input이 들어온다면 상상도 하기 싫다....

두 번째 아이디어

여기서 부터 감이 잡히기 시작한다.

 

일단 글자수에 따른 MOO 반복을 최소 몇 번 해야 하는지에 대한 수식을 찾아내야 했다.

만약 11번째 글자를 찾고 싶다면

         여기
          ↓
MooMoooMooMooooMooMoooMoo

최소 k = 2번 반복 되어야 한다.

k = 0 Moo (3글자)
k = 1 MooMoooMoo (10글자)
k = 2 MooMoooMooMooooMooMoooMoo (25글자)

이걸 어떻게 구해야 할까 고민 했다, 일단 처음은 3글자 변수는 tot

while(1){
  if(tot < n){
    tot = tot * 2 + (cur+3);
    cur++;
    continue;
  }
  break;
}

tot가 찾는 글자수 보다 적다면 

tot = tot * 2 + (cur+3);

위의 방법 처럼 최소 글자수를 구해 준다

cur 변수는 최대 반복 횟수를 알려주는 변수이다

위 처럼 하면 최소 글자수와 최소 반복 횟수를 구해 줄 수 있다.

 

자 이제 어떻게 글자를 찾아 줄 것인가를 고민해야 한다.

3개로 나눠 줄 수 있다.

Moo/Mooo/Moo
MooMoooMoo/Moooo/MooMoooMoo
MooMoooMooMooooMooMoooMoo/Mooooo/MooMoooMooMooooMooMoooMoo

오른쪽 / 가운데 / 왼쪽 이렇게 3개로 항상 나눌 수 있다.

가운데를 가운데 시작을 half로 정해주고 가운데 끝을 endHalf로 정해준다

         half endHalf
          ↓     ↓ 
MooMoooMoo/Moooo/MooMoooMoo

  int half = (tot/2) - (x+3)/2 + 1;
  int endHalf = half + (x+2);

 

찾는 글자가 왼쪽 가운데 오른쪽 어디에 있는지 결정한다

// 찾는 글자가 외쪽에 있을 때
  if(n < half){
    tot -= (tot-half)+1;
    moo(x-1);
  }
  // 찾는 글자가 가운데라면
  else if(half <= n && n <= endHalf){
    if(n == half)cout << "m";
    else cout << "o";
  }
  //찾는 글자가 왼쪽에 있다면
  else if (n > half){
    n -= endHalf;
    tot -= endHalf;
    moo(x-1);
  }

왼쪽에 있다면 총길이를 변경해줘야 한다.

 

CODE

//Moo 게임
#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
//횟수 
int n;
int tot = 3;
void moo(int x){
  if(x == 0){
    if(n == 1)cout <<"m";
    else cout << "o";
    return;
  }
  //가운데 컨텍스트의 시작 부분
  int half = (tot/2) - (x+3)/2+1;
  int endHalf = half + (x+2);

  // 찾는 글자가 외쪽에 있을 때
  if(n < half){
    tot -= (tot-half)+1;
    moo(x-1);
  }
  // 찾는 글자가 가운데라면
  else if(half <= n && n <= endHalf){
    if(n == half)cout << "m";
    else cout << "o";
  }
  //찾는 글자가 왼쪽에 있다면
  else if (n > half){
    n -= endHalf;
    tot -= endHalf;
    moo(x-1);
  }
  return;
}

int main(){
  init();
    cin >> n;
    tot = 3;
    int cur = 1;
    while(1){
      if(tot < n){
        tot = tot * 2 + (cur+3);
        cur++;
        continue;
      }
      break;
    }
    moo(--cur);
  return 0;
}