[BOJ 5904] Moo 게임 (C++)

www.acmicpc.net/problem/5904

5904번: Moo 게임

Moo 게임 문제

구현 방법

처음에 이 문제를 봤을 때, 재귀를 통해 moo수열 문자열을 만들어서, 입력한 n 번째의 알파벳을 출력하면 되는 줄 알았습니다.

 

재귀를 통해 Moo 수열을 구현하는 코드를 성공적으로 짜고 기뻐하면서 제출했을때, 결과는 메모리 초과였습니다.

 

생각해보니 입력 n은 최대 1억 까지 가능한데, 길이가 1억인 수열을 구하려면 재귀를 너무 많이 돌아야 돼서 메모리 초과가 날 것 같았습니다.

 

문자열을 구하겠다는 생각을 바꿔, 입력 n이 들어오면, n이 몇 번째 수열의 어디부분에 있는지 파악해 n번째 알파벳이 m인지 o인지 출력해주도록 구현했습니다.

 

설명을 쉽게 하기 위해 예시를 들어보겠습니다.

 

예를 들어 문제에서 주어진 S(2)수열은 다음과 같습니다.

 

m o o m o o o m o o m o o o o m o o m o o o m o o

 

다음 수열은 3가지 파트로 나뉘어 집니다.

 

m o o m o o o m o o m o o o o m o o m o o o m o o

 

• 이전 문자열, 즉 S(k-1)
• o가 k+2개인 문자열
• 이전 문자열, 즉 S(k-1)

---

만약 구하고 싶은 n번째 원소가 첫 번째 파트인 이전 문자열, 즉 S(k-1)의 범위에 포함된다면 다음에 탐색 할 범위를 이전 문자열의 범위로 바꿔줍니다.

 

이는 현재 수열의 전체 길이를 이전 문자열의 크기만큼 줄이고, o가 k+2개인 문자열에서 1을 빼서 o가 k+1인 문자열로 만들어 줍니다.

 

 

(현재 수열의 전체 길이를 이전 문자열의 크기만큼 줄이면서 노란색 이후는 고려하지 않겠다)

m o o m o o o m o o m o o o o m o o m o o o m o o

↓

m o o m o o o m o o

 

 

이렇게 하면 다음 탐색의 범위는 m o o m o o o m o o가 됩니다.

---

만약 구하고 싶은 n번째 원소가 두 번째 파트인 o가 k+2개인 문자열의 범위에 포함된다면 정답을 바로 알 수 있습니다.

정답은 입력한 n에서 이전 문자열의 크기를 빼고, 결과가 1이면 m을 출력하고, 아니면 o를 출력하면 됩니다.

아까 들었던 예를 가지고 설명해 보겠습니다.

 

m o o m o o o m o o m o o o o m o o m o o o m o o

 

여기서 빨간색으로 표시된 o는 수열의 13번째입니다.

이때 13에서 이전 문자열의 크기인 10을 빼면 3입니다. 즉 이전 문자열을 제거하는 것이죠.

13에서 이전 문자열의 크기를 빼서 3이니 o를 출력하면 됩니다.

---

마지막으로 구하고 싶은 n번째 원소가 세 번째 파트인 이전 문자열, 즉 S(k-1)의 범위에 포함된다면 첫 번째와 마찬가지로 탐색 범위를 이전 문자열로 바꿔줍니다.

 

이는 첫 번째와는 다르게 현재 수열의 전체 길이에서 (이전 문자열의 크기 + o가 k+2개인 문자열의 크기)만큼 줄이고, o가 k+2개인 문자열에서 1을 빼서 o가 k+1인 문자열로 만들어 줍니다.

즉 우리 예시에서,

 

이전 문자열의 크기   o가k+2개 크기                          

m o o m o o o m o o m o o o o m o o m o o o m o o

↓

m o o m o o o m o o

 

 

위 내용을 아래 소스코드처럼 구현했습니다.

 

소스코드에 주석을 넣어서 이해하기 쉽게 설명했습니다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;


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

    //입력한 n 이 몇 번째 수열에 포함되는지?
    //totLength = 수열 전체 길이, midLength = o가 k+2개인 부분 길이
    //초기 상태 : moo
    int totLength = 3;
    int midLength = 3;

    //n이 현재 수열의 길이보다 크면 수열 계속 늘려주기
    while(n > totLength) {
        totLength = totLength*2 + ++midLength;
    }

    while(1) {
        //t 는 이전 문자열의 길이
        int t = (totLength-midLength)/2;

        //n이 첫 번째 부분이면
        //o가 k+2개인 부분의 길이를 1 줄여주고, 전체 길이를 이전 문자열의 길이로
        if(n <= t) {
            midLength--;
            totLength = t;
        }//n이 세 번째 부분이면
        //이전 문자열의 길이 만큼 줄여주며 사라진 만큼 n도 줄여준다
        //o가 k+2개인 부분의 길이를 1 줄여주고, 전체 길이를 이전 문자열의 길이로
        else if(n > t + midLength) {
            n -= t + midLength;
            midLength--;
            totLength = t;
        }//n이 중간 부분이면
        //n에서 이전 문자열의 크기만 빼준다.
        else {
            n -= t;
            break;
        }
    }

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

}