[PS 백준 - 4.5] 5904번: Moo 게임

문제 정보

백준 5904번 - 바로가기

• 난이도: 실버 1
• 알고리즘: 분할 정복

코멘트

이 문제는 내가 백준을 초반에 풀기 시작했을 때 무턱대고 덤볐다가 틀려서 6개월간 방치해두었던 문제이다. 근데 이번 스터디를 하면서 분할 정복을 배우고 푸니까 한번에 맞았다!

moomooomoomoooomoomooomoomooooomoomooomoomoooomoomooomoo
<3, 4, 3, 5, 3, 4, 3>, 6, <3, 4, 3, 5, 3, 4, 3, 6>

1. 왼쪽 구간을 제 1 구간, 가운데 구간을 제 2 구간, 오른쪽 구간을 제 3구간으로 잡았다.
2. 제 1 구간에 있으면 그대로, 제 3 구간에 있으면 제 2 구간의 길이 + 제 3 구간의 길이 만큼 삭제해서 옮겨주었다.
3. 제 2 구간에 있으면 제 1 구간의 길이를 삭제하고 break 하고 n이 1이면 "m"을, 아니면 "o"를 출력한다.

소스 코드

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int main() {
	int n;
	cin >> n;

	int arr1[29]{ 0, };
	int arr2[29]{ 0, };

	int tmp = 0;
	
	for (int i = 0; i < 29; i++) {
		arr1[i] = tmp;
		int x = tmp + (i + 3);
		tmp *= 2;
		tmp += (i + 3);
		arr2[i] = x;
	}

	int idx = 0;
	for (int i = 28; i > 0; i--) {
		if (n > arr2[i]) {
			idx = i;
			break;
		}
	}

	for (int i = idx; i >= 0; i--) {
    
		// 제 2 구간 [중간]
		if (n > arr1[i] && n < arr2[i]) {
			n -= arr1[i];
			break;
		}
        
		// 제 1 구간
		else if (n <= arr1[i]) {
			continue;
		}
		
		// 제 3 구간
		else if (n > arr2[i]) {
			n = n - arr2[i];
			idx--;
		}
	}

	if (n == 1) cout << "m";
	else cout << "o";
}