[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段を削除して切断し、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";
}