[C++] 백준 16440번 제이크와 케이크

케이크를 잘라서 과일을 두명에게 공평하게 나누어주기 위해서
몇번의 칼질이 필요하고 어디를 잘라야하는지 찾는 문제입니다.

여기서 답은 1번 또는 2번만 나올 수 있습니다.
1번의 경우 가운데를 자르는 경우이며,
2번의 경우 가운데가 아닌 두 군데를 자르는 경우입니다.

1번은 가운데를 중심으로 왼쪽의 과일의 개수를 전부 더해서
각 과일의 개수가 동일하면 1번으로 처리합니다.

2번은 1번이 아닌경우 n/2개씩 과일의 개수의 합이 같은 경우를 찾습니다.
그리고 같은 경우에 왼쪽과 오른쪽 부분을 자르면 됩니다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int main(int argc, char* argv[])
{
	int n;
	int a = 0;
	int b = 0;
	string s;

	cin >> n;
	cin >> s;

	for (int i = 0; i < n / 2; ++i) {
		if (s[i] == 's') {
			++a;
		}
		else {
			++b;
		}
	}

	if (a == b) {
		cout << "1" << endl;
		cout << n / 2 << endl;
	}
	else {
		cout << "2" << endl;
		for (int i = n / 2; i < n; ++i) {
			if (s[i] == 's') {
				++a;
			}
			else {
				++b;
			}

			if (s[i - n / 2] == 's') {
				--a;
			}
			else {
				--b;
			}

			if (a == b) {
				cout << i - n / 2 + 1 << " " << i + 1<< endl;
				break;
			}
		}
	}

	return 0;
}