문제 정보

백준 BOJ 17297번 Messi Gimossi 문제 링크 : https://www.acmicpc.net/problem/17297 선린인터넷고등학교 제3회 천하제일 코딩대회 예선 E번

문제 풀이

이번 문제는 규칙을 찾아 내는게 가장 핵심인 문제입니다.

우선적으론 글자를 이어 붙여 할 생각은 접는게 좋습니다.

그래서 글자 수를, 피보나치로 만들어 배열에 저장해둡니다.

	pibo.push_back(5);
	pibo.push_back(13);

	while (w < 1073741824) {
		e = w;
		w = w + q+1;
		q = e;
		pibo.push_back(w);
	}

이렇게요

그다음엔 무엇을 해야 하는가?

n 이 만약에 21이라고 생각을 해봅시다.

pibo[0] = 5,

pibo[1] = 13

pibo[2] = 19

pibo[3] = 33

입니다.

n 보다 큰 최초의 pibo 를 구해주면 되는데요

21이라면, pibo[3]이겠죠?

pibo[3] 은 어떻게 만들어질까요?

pibo[2] + pibo[1] 입니다.

구역을 나누자면 [ pibo[i-1]개 / pibo[i-2개 ]

로 나누어 지겠죠.

그럼 이제 pibo[i-1] 개로 기준을 나눕니다.

n 이 이거보다 크냐 작냐로 나누면 되요.

만약에 n이 pibo[i-1] 보다 작다면

[ pibo[i-1] V여기어딘가 / pibo[i-2] ] 안에 있는 겁니다.

그러면 그대로 i만 -1 해서 탐색을 해줍니다.

반대로 pibo[i-1] 보다 크면

[pibo[i-1] / pibo[i-2] 어딘가] 에 있겠죠

그러면 앞에 pibo[i-1] 부분은 볼 필요가 없습니다.

앞에 부분을 버려버리고 pibo[i-2] 부분으로 넘어가 주면 됩니다.

예시를 들어볼께요

pibo[2] = 19 n = 21

n 이 pibo[2]보다 큼으로

n은 pibo[1] 에 속한다고 보고

21 - 19 해주면

pibo[1] 의 2번째 와 같습니다.

그럼 pibo[1] 의 2번째를 출력 해 주면 됩니다.

만약 수가 더 크다면?

반복문을 통해서 아래까지 쭉쭉 내려와 주시면 됩니다.

그러면 간단하게 문제가 해결이 됩니다. !

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
	string b;
	int n;
	int q;
	int w;
	int e;
	int i;
	vector<int> pibo;
	b = "Messi Gimossi";

	q = 5;
	w = 13;
	pibo.push_back(5);
	pibo.push_back(13);

	while (w < 1073741824) {
		e = w;
		w = w + q+1;
		q = e;
		pibo.push_back(w);
	}

	cin >> n;
	i = 0;
	while (pibo[i] < n)
		i++;
	while ( i >= 2) {
		if (n == pibo[i - 1] + 1) {
			n = -1;
			break;
		}
		if (n > pibo[i - 1]) {
			i -= 2;
			n -= pibo[i + 1]+1;
		}
		else
			i -= 1;
	}

	if (n == -1 || n == 6) {
		cout << "Messi Messi Gimossi";
	}
	else {
		cout << b.at(n - 1);
	}

	return 0;
}