[백준] 16440 제이크와 케이크

쉬운건줄 알고 하다가 틀리고 털렸다

이 문제는 수학적으로 k=1 or k=2로 풀 수 있다고 한다

k=1이라면 중앙을 잘라보고 확인하면 된다

 

k=2라면 절반 한조각과 나머지 절반을 만들 2조각이 나온다

그럼 1부터 N까지 보다 절반이 될 한조각을 찾으면 된다

 

과일 2개가 정확히 반반씩 있기 때문에 1~N까지 보다보면 

길이가 N/2이고 과일을 반반씩 갖는 구간이 무조건 나온다고 한다..!!

나는 몰랐는데..!! 수학이란... 배워간다..

 

소스코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int n;
string s;
 
int main(){
    //freopen("input.txt","r",stdin);
    cin>>n>>s;
    int cnt=0;
    for(int i=0;i<n/2;i++)
        if(s[i]=='s') cnt++;
    if(cnt==n/4){
        puts("1"); printf("%d\n",n/2);
    }
    else {
        for(int i=n/2;i<n;i++){
            if(s[i]=='s') cnt++;
            if(s[i-n/2]=='s') cnt--;
            if(cnt==n/4){
                puts("2");
                printf("%d %d\n",i-n/2+1,i+1);
                break;
            }
        }
    }
}