[백준 5904] Moo 게임

www.acmicpc.net/problem/5904

5904번: Moo 게임

나이브하게 접근하면 tle 뜬다 변수를 사용하지 않고 같은 로직을 사용해도 런타임에러 뜬다...왜지....

 

접근방법:

k번째 moo 수열 S(k)은 크게 A, B, C 세 부분으로 구성된다.

S(k-1 ) + (m + o * (k+2)) + S(k-1)

 

 

k-1번째 수열이 앞뒤로 있고 중간에 m하나와 o가 k+2개 존재한다.

이 점을 사용하여 n의 값에 따라 적절한 위치로 n을 보내 줄 것이다.

 

먼저 n길이 이상의 moo 수열이 나오도록 k와 그 때 길이 len을 계산한다.

 

n의 위치는 

n<=tmp면 A부분에, 

n>tmp + k + 3이면 C부분에, 

나머지 경우엔 B부분에, 라고 할 수 있다.

 

B부분인 경우 첫 글자만 m이고 나머지는 o이다.

A부분이면 길이를 재조정해준다.

C부분이면 n을 감소시켜 A와 동일하게 만들어준다.

 

#include <stdio.h>
using namespace std;

long long n;
char result;

int main(void)
{
  scanf("%lld", &n);

  long long len = 3;
  long long k = 0;
  while (n > len)
  {
    k++;
    len = len * 2 + k + 3;
  }

  while (1)
  {
    long long tmp = (len - k - 3) / 2;

    if (n <= tmp)
    {
      k--;
      len = tmp;
    }
    else if (n > tmp + k + 3)
    {
      n -= tmp + k + 3;
      k--;
      len = tmp;
    }
    else
    {
      if (n == tmp + 1)
      {
        result = 'm';
      }
      else
      {
        result = 'o';
      }
      break;
    }
  }

  printf("%c\n", result);

  return 0;
}