[백준알고리즘] 5904번: Moo 게임 -C++

[백준알고리즘] 5904번: Moo 게임 -C++

5904번: Moo 게임 (acmicpc.net)

5904번: Moo 게임

분할 정복 문제로, 이래저래 고민하다가 길이를 기준으로 재귀적으로 풀었다. 최악의 경우라도 수의 범위나 시간이 재귀적으로도 충분할 것이라 생각했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

문제에서 주어진 조건을 이용했다.

• \(M(k) =\ 'o'가\ k+2개인\ mo..o\ 문자열\)
• \(S(k) = S(k-1) + M(k+1) + S(k-1)\)

 

따라서, \(k\)가 주어졌을 때 \(S(k)\)에서 확실히 'm'인 위치는 아래의 세 가지 경우다.

1. 수열이 시작하는 가장 처음 부분(idx = 0)
2. \(S(k-1)\)이 끝나고, \(M(k+1)\)이 시작하는 부분
3. 마지막 \(S(k-1)\)이 시작하는 부분

 

첫 번째 조건은 사실 맨 처음 \(S(k-1)\)이 시작하는 위치와 같은 것을 말한다. 해당 조건들을 기준으로는 확실히 'm'인 것을 알 수 있다. 추가적으로, \(M(k+1)\)의 시작 위치를 제외하고는 나머지 부분이 'o'라는 것도 알고 있다.

 

그러나, \(S(k-1)\) 내부에서는 정확히 어느 위치에서 'm'이 위치해있는지 모른다. 이를 알기 위해서 재귀적인 방식을 적용했다.

 

이때 주의할 점은 재귀적으로 호출할 때 찾으려는 위치 \(N\)의 실질적인 인덱스가 바뀔 수 있다는 것이다. 항상 \(S(k)\)의 인덱스는 0부터 시작하는 것으로 계산할 것이기 때문에, 마지막에 더해지는 \(S(k-1)\)에 대해 재귀적으로 호출할 때 찾으려는 \(N\)의 인덱스는 바뀌어야 한다.

 

나머지는 아래 코드와 주석으로 쉽게 볼 수 있을 것이다.

#include <cstdio>
#include <vector>

std::vector<int> vecLength;

bool isMChar(const int k, const int idx);

int main(void) {
	/* 입력 */
	int N;
	scanf("%d", &N);

	/* 수열의 길이값 사전 계산 */
	vecLength.push_back(0); // 초기값
	for ( int iMooLength = 3; vecLength.back() < N; ++iMooLength ) {
		vecLength.push_back(vecLength.back() * 2 + iMooLength);
	}

	/* 출력 */
	printf("%c", (true == isMChar(vecLength.size() - 1, N - 1)) ? 'm' : 'o');

	return 0;
}

/* S(k)에서 idx의 값이 'm'인지 확인 */
bool isMChar(const int k, const int idx) {
	bool bRet = false;

	int currLength = vecLength[k];				// S(k)의 길이
	int beforeLength = vecLength[k - 1];		// S(k-1)의 길이

	int iHeaderIdx = 0;							// 1. 시작 위치
	int iBodyIdx = beforeLength;				// 2. M(k+1) 시작 위치
	int iTailIdx = currLength - beforeLength;	// 3. 마지막의 S(k-1) 시작 위치

	if ( iHeaderIdx == idx || iBodyIdx == idx || iTailIdx == idx ) {
		bRet = true;
	}
	else if ( idx < iBodyIdx ) {
		bRet = isMChar(k - 1, idx);
	}
	else if ( iTailIdx < idx ) {
		bRet = isMChar(k - 1, idx - iTailIdx); // 인덱스값 변경
	}
	else {
		bRet = false;
	}
	
	return bRet;
}