[백준 17297] - Messi Gimossi(C++)[골드3]

📕문제

---

메시는 축구 선수이다. 메시는 기분이 좋다.

messi(1): Messi

messi(2)​​: Messi Gimossi

messi(3)​​​​​​: Messi Gimossi Messi

messi(4): Messi Gimossi Messi Messi Gimossi

messi(5): Messi Gimossi Messi Messi Gimossi Messi Gimossi Messi

메시의 외침은 피보나치수열과 유사하게 정의된다. messi(N)은 messi(N-1), 공백, messi(N-2)을 차례로 이어 붙여서 만든 문자열이다.

욱제는 N이 충분히 클 때, messi(N)의 M번째 글자가 뭔지 궁금해졌다.

📗입력

---

정수 M이 주어진다. (1 ≤ M ≤ 230-1)

📗출력

---

N이 충분히 클 때, messi(N)의 M번째 글자가 공백(' ')이 아닐 경우에는 그 글자를 출력한다.

M번째 글자가 공백(' ')일 경우에는 Messi Messi Gimossi를 출력한다.

정답은 대소문자를 구분하므로 출력에 주의한다.

👀문제 해석

• 이 문제도 분할정복으로 풀 수있다.
• 저번에 풀었던 레벨 햄버거와 유사한 문제이다.
• 문자열을 어떻게 분할하는지가 관건인 문제이다.

🔎문제풀이

1 : Messi
2 : Messi Gimossi
3 : Messi Gimossi Messi
4: Messi Gimossi Messi Messi Gimossi

• 우선 문제에서 N이 주어지지는 않는다. M을 통해서 우리는 N을 뽑아내야 한다.
  • 메시 수열은 피보나치수열과 유사하다.
  • 규칙은 N = N-1 + 1(공백) + N-2이다.
  • 이렇게 반복문을 돌려서 수열의 글자크기가 M을 넘을 때의 N을 추출한다.
• 그다음은 문자열을 쪼갠다.
  
  • 종료조건은 M의 크기가 "Messi Gimossi"의 글자크기보다 작거나 같을 때입니다. 
  • 즉 M이 13과 작거나 같을 때 종료해주시면 됩니다.

• 우리가 찾고자 하는 글자(M)는 N번째 수열에서 3가지 구간에 걸치게 된다.
  1. (N-1) 번째 문자열의 구간
     • (N-1) 번째 문자열에 속하기에 (N-1)문자열로 접근하고,  M은 값을 유지한다.
  2. V인 구간
     • V인 구간은 (N-1)번째 문자열의 길이 +1와 동일하고, 그때는 문제에서 요구하는 문자열을 출력하면 된다.
  3. (N-2) 번째 문자열의 구간
     • (N-2)번째 문자열에 속하기 때문에 (N-2) 문자열로 접근해야 하고, M값은 (N-1) 문자열의 길이와 공백을 포함한 값을 빼줘야 한다.

전반적인 알고리즘은 이러하지만 이해하기 쉽게 예를 들어서 설명하겠습니다.

아래 사진은 N=3인 문자열입니다.

가정으로 3가지 경우를 하겠습니다.

1. M이 (N-1) 구간인 경우 
   • M은 N=2인 구간에 속하게 됩니다.
   • 그럼 우리는 2번째 수열로 접근해서 M에 접근을 하면 됩니다. 
2. M이 V구간인 경우
   • M에 값은 (N-1)의 길이+1과 같은 경우입니다.
   • 이 경우는 바로 요구하는 문자열을 출력하면 됩니다.
3. M이 (N-2) 구간인 경우
   • 예를 들어서 M값이 15라고 가정합시다. 
   • 우리는 (N-2) 구간이기 때문에 (N-2) 문자열로 접근을 해야 합니다.
   • 하지만 M값을 조정해줘야 합니다.
   • 그래서 앞에 글자수들을 다 날려주는 겁니다. => (N-1) 문자열의 길이 +1 만큼 M값에서 빼줍니다.
   • 그럼 이제 M은 1이 되고, (N-2) 문자열에서 첫 번째 글자를 가리키게 됩니다.

💻코드

/*
골드3 메시기모띠
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int M;
vector<int> f1;
string result = "Messi Gimossi";
int search(int Step, int order);
int main()
{
    cin >> M;
    f1.push_back(5);  //Messi
    f1.push_back(13); //Messi Gimossi
    int a = 5;
    int b = 13;
    int mm = 0;
    while (mm < M)
    {
        mm = a + b + 1;     //(n-1)+1+(n-2)
        a = b;
        b = mm;
        f1.push_back(mm);
    }
    int size=f1.size();
    int answer = search(size, M);
    if (answer == -1 || answer == 6)
    {
        cout << "Messi Messi Gimossi" << endl;
    }
    else
        cout << result[answer - 1];    
}
int search(int Step, int order)
{
    // 이제 쪼개주기.    
    if (order <= f1[1])
        return order;
    if (order <= f1[Step - 1]) // N-1구간
        return search(Step - 1, order);
    else if (order == f1[Step - 1] + 1) // 공백
        return -1;
    else //N-2구간
        return search(Step - 2, order - f1[Step - 1] - 1);
}

 

✔느낀 점

• 분할정복은 다 비슷한 맥락의 문제인 것 같다.
• 저번에 푼 레벨 햄버거와 유사한 알고리즘이어서 쉽게 풀 수 있었다.
• 분할정복은 손으로 몇 가지 경우의 수를 테스트해보고, 쪼개는 구간을 재귀적으로 잘 표현하면 된다.