[백준 5904] Moo 게임

난이도

골드 V

📜문제

https://www.acmicpc.net/problem/5904

🔎접근

1. ❌ 규칙적으로 길이가 늘어나기 때문에 전체적으로 문자열을 구한다음 그 위치에 맞는 문자를 찾는다. (메모리초과)
2. ⭕ 마찬가지로 규칙적으로 늘어나기 때문에 반대로 줄여가면서 위치를 찾을 수 있다.

🌞풀이

❌틀린 풀이1

맨처음에는 전체 길이를 다 구해서 찾으려고 했다.
그런데 입력이 10억까지 들어갈 수 있기 때문에 당연히 메모리 초과가 났다.

#include <iostream>

using namespace std;

string mid_moo = "moo";

int Cal_times(int N)
{
	int time = 0;

	int len = 3;
	int middle_moo = 3;

	while (len < N)
	{
		len = len * 2 + (middle_moo + 1);
		middle_moo++;
		time++;
	}
	return time;
}

void Moo(string sentence, int time, int N)
{
	string test = "";
	mid_moo += "o";

	if (time)
	{
		sentence = sentence + mid_moo + sentence;
		Moo(sentence, time - 1, N);
	}
	else if (time == 0)
	{
		cout << sentence[N-1];
	};

}
int main()
{
	int N = 0;
	cin >> N;

	int time = Cal_times(N);

	string s = "moo";
	Moo(s, time, N);

	return 0;
}

❌틀린 풀이2

전체를 다 구해서 푸는 방식이 잘못됐다고 인지하고 일단 N이 필요한 길이까지 늘린다음 찾아야 하는 위치가 있는 부분을 경우로 구분해 나눠가면서 길이를 줄여나갔다.
그런데 이 방식은 런타임 에러가 났다.

#include <iostream>

using namespace std;

int moo = 0;
int middle = 3;
int total = 3;

char moo_func(int len)
{
		if (len < moo) // first
		{
			total = moo;
			middle--;
			moo = (total - middle) / 2;
			moo_func(len);
		}
		else if (len > moo + middle) // third
		{
			len -= moo + middle;
			total = moo;
			middle--;
			moo = (total - middle) / 2;
			moo_func(len);
		}
		else // second
		{
			len -= moo;
			total = middle;
			if (len == 1) return 'm';
			else return 'o';
		}
		if (len <= 3)
		{
			if (len == 1) return 'm';
			else return 'o';
		}
}


void cal_len(int N)
{
	while (1)
	{
		total = moo * 2 + middle;
		if (N < total) break;
		moo = total;
		middle++;
	}
}

int main()
{
	int N = 0;
	cin >> N;
	cal_len(N);
	cout << moo_func(N) << "\n";

	return 0;
}

⭕ 맞은 풀이

이 방식은 결국 검색을 해서 풀었다. 풀이 참고 사이트

결국은 중간부분이 나온다면 바로 출력을 하고 아니라면 재귀적으로 다시 함수호출을 해서 구하는 방식이다.

#include <iostream>

using namespace std;

string Moo = "moo";

void Cal_MOO(int N, int cnt, int len)
{
	int new_len = len * 2 + (cnt + 3);
	if (N <= 3)
	{
		cout << Moo[N - 1] << "\n";
		exit(0);
	}
	if (N > new_len)
	{
		Cal_MOO(N, cnt + 1, new_len);
	}
	else
	{
		if (N > len && N <= len + cnt + 3) // second
		{
			if (N - len != 1) cout << "o\n";
			else cout << "m\n";
			exit(0);
		}
		else Cal_MOO(N - (len + cnt + 3), 1, 3);
	}
}

int main()
{
	int N = 0;
	cin >> N;

	Cal_MOO(N, 1, 3);

	return 0;
}

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기