[BOJ 16440] 제이크와 케이크

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

16440번: 제이크와 케이크

 

- 문제 요약

 

제이크는 레이니콘으로부터 긴 모양의 케이크를 선물 받았습니다.

케이크 위에는 N개의 과일 조각이 올려져 있는데 케이크 위에는 딸기 N/2개와 키위 N/2개가 일정한 간격을 두고 일렬로 올려져 있습니다. 여기서 N은 4의 배수입니다.

제이크는 케이크를 핀과 올려진 과일의 종류를 포함하여 케이크를 정확히 절반씩 먹기 위해 받은 케이크를 잘라서 나누어 가지려고 합니다. 이때 제이크가 받은 딸기가 N/4개여야 하며 키위도 N/4개 있어야 합니다. 핀도 제이크와 같은 개수의 딸기와 키위를 받아야 합니다.

제이크와 핀은 케이크를 자르기 귀찮으므로 그 횟수를 최소화하고자 합니다. 핀과 제이크가 똑같이 나누어 먹기 위해 케이크를 잘라야 하는 최소 횟수와 방법을 알려주세요.

 

 

- 알고리즘 정리

 

과일들의 가운데를 자르는 경우, 왼쪽의 딸기, 키위 수를 더해 같은지를 확인해 줍니다.

만약 같다면 그대로 1과 n/2(가운데)를 출력해 주고, 같지 않다면 n/2개씩 과일의 개수를 확인해 줍니다.

과일의 개수가 같다면 그 위치를 기준으로 왼쪽과 오른쪽 부분을 잘라주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,S,K;
string s;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>s;
	for(int i=0;i<n/2;i++){
		if(s[i]=='s'){
			S++;
		}
		else{
			K++;
		}
	}
	if(S==K){
		cout<<1<<'\n'<<n/2;
	}
	else{
		cout<<2<<'\n';
		for(int i=n/2;i<n;i++){
			if(s[i]=='s'){
				S++;
			}
			else{
				K++;
			}
			if(s[i-n/2]=='s'){
				S--;
			}
			else{
				K--;
			}
			if(S==K){
				cout<<i-n/2+1<<" "<<i+1;
				break;
			}
		}
	}
}

코드 제출 결과

후기 : 이게 되네