백준 5904 Moo 게임

작성일 | In |

Problem : Moo 게임

유형 : 분할 정복

문제 해석

  • Moo 수열에서 N번째 글자를 구하라.

문제 재해석

  • N이 10억이다.
  • 단순하게 나이브하게 구현해서는 답을 도출 해낼 수 없다.
  • S(N)은 S(N-1) + M + O x (n + 2) + S(N-1) 으로 이루어진다.

해결 전략

이미지

  • S(N) 은 재귀적으로 반복 되어 진다는 것을 알 수 있다.
  • 먼저 10억 이하가 될 수 있는 모든 S(N)의 길이를 구한다.
  • N이 속하는 S(N)의 길이를 찾은 뒤,
    • S(N-1) 구간에 속하는지,
    • Moo.... 구간에 속하는지를 구분한다.
  • S(N-1) 구간에 속한다면, 재귀적으로 계속 찾아나간다.

설계, 구현

  • 기저사례의 경우는, 3보다 작은 경우다.
  • 3보다 클경우, 길이를 저장한 MooLen을 통해 어느 S(M)에 속하는지 찾는다.
  • Moooo 구간에 속한 경우, 첫번째만 m 이고 나머지는 o 로 처리 해준다.
  • 그 뒤의 구간에 속한다면, S(M-1) 구간에서 다시 찾아나간다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll MooLen[100];

char Solve(ll n) {
    if (n <= 3) {
        if (n == 1) return 'm';
        else return 'o';
    }

    ll m = 1;
    while (n > MooLen[m]) {
        m++;
    }

    if (n <= MooLen[m] - MooLen[m - 1]) {
        if (n - MooLen[m - 1] == 1) return 'm';
        else return 'o';
    }

    return Solve(n - MooLen[m - 1] - (m + 3));
}

void Input() {
    ll n;
    cin >> n;
    MooLen[0] = 3;
    for (ll i = 1; i < 100; ++i) {
        MooLen[i] = MooLen[i - 1] * 2 + (i + 3);
        if (MooLen[i] > 1e9) break;
    }
    cout << Solve(n);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    Input();

    return 0;
}

피드백

  • 분할정복 문제는 역시 훈련이 더 필요해 보인다.
  • 구간별로 나누어서 계산을 할 수 있다면 분할정복 솔루션을 생각해보자.