https://www.acmicpc.net/problem/17297
문제
> 메시는 축구 선수이다. 메시는 기분이 좋다.
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번째 글자가 뭔지 궁금해졌다.접근
각 N에 대한 문자열의 길이는 N-1번쨰의 길이 + 공백 1글자 + N-2번째의 길이가 된다. 입력받은 M이 어떤 번째에 속하는지 알기 위해 M보다 더 길어지는 경우 까지 문자열의 길이를 구해본다.
예를들어 M이 25라고 하면 이 25번쨰를 알기 위해서 25보다 더 긴 첫문자열의 길이가 필요하고, 이 문자열은 N-1+1+N-2로 이루어져 있으므로 세 분기로 나누어 N-1보다 작거나 같으면 N-1번째 문자열 안에 포함되어 있고, N-1+1이면 공백이므로 특정 문자열 출력, N-1+1보다 크면 N-2번째 문자열에 있다는 뜻이다.
이 각각의 N, N-2등등의 문자는 결국 분할정복으로 줄여나가면 1번째, Messi와 2번째 messi Gimossi로 이루어져 있다.
따라서 M을 통해 구해낸 길이의 인덱스를 줄여나가며 인덱스가 0 또는 1이 될 떄까지 줄이고, 1이면 2번째 문자열에서 해당 자리수를, 0이면 1번째 문자열에서 해당 자리수를 찾는다.
문제해결
> 1번문자열과 2번 문자열을 messi1과 messi2에 저장해둔다.
> M을 입력받고 해당 M보다 첫번 쨰로 긴 문자열의 길이까지 N번째 문자열의 길이를 저장하는 벡터 N에 저장해나간다.
> 그럼 M은 N배열의 마지막 원소 안에 포함 되어 있다는 뜻이므로 idx를 size()-1로 잡아준다.
> idx가 0또는 1이면 messi1, messi2에 포함된다는 뜻이므로 1보다 클 때까지만 while문을 돌린다.
> M이 N-1번째 +공백1개의 길이보다 클 때, 더 이상 N-1과 공백은 필요없으므로 N-2번쨰를 이루는 N-3과 N-4를 보기위해
M에서 N-1번째의 길이 + 1만큼을 빼 갱신해준다.
> 그리고 idx도 2를 뺴서 N에서 N-2번째를 가리키게 갱신해준다.
> 위 경우 말고 M이 공백을 가리키는 N-1번째의 길이 +1 이면 문제에 주어진 문자열을 출력하고 실행을 종료한다.
> 마지막으로 N-1번째에 속할 떄 이다. M은 변하지 않고, N-1을 이루는 N-2, N-1중 또 어디에 속하는지 보기위해 idx만 1감소 해주고 넘어간다.
> 이제 idx가 0또는 1이 되면 각각 messi1과 messi2를 가리킨다.
> 0은 그대로 messi1중 M번째를 출력하고 1은 중간의 공백을 생각해 6이면 특정 문자열 출력하고 아니면 M번째를 출력한다.코드
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int M;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> M;
vector<long long> N = { 5, 13 };
string messi1 = "Messi";
string messi2 = "Messi Gimossi";
while (M > N[N.size() - 1]) N.push_back(N[N.size() - 1] + 1 + N[N.size() - 2]);
int idx = N.size() - 1;
while (idx > 1)
{
if (M > N[idx - 1] + 1) {
M -= (N[idx - 1] + 1);
idx -= 2;
}
else if (M == N[idx - 1] + 1) {
cout << "Messi Messi Gimossi" << '\n';
exit(0);
}
else {
idx -= 1;
}
}
if (idx == 1) {
if(M == 6) cout << "Messi Messi Gimossi" << '\n';
else cout << messi2[M - 1] << '\n';
}
else {
cout << messi1[M - 1] <<'\n';
}
}
후기
인덱스와 번째를 갈라주고 분할해주는게 머릿속에서 계속 꼬여서 복잡했다.
