KOI 2021년 1차대회 초등부

21756번: 지우개

풀이

진짜 진짜..  그냥 시뮬레이션 돌리자. 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int A[103];
int main(){
    int N,ans;
    scanf("%d",&N);
    for(int i=1;i<=N;i++)A[i]=i;
    while(1){
        int cnt=0;
        for(int i=1;i<=N;i++){
            if(A[i]){
                cnt++;
                ans=A[i];
            }
            if(cnt%2)A[i]=0;
        }
        if(cnt==1)break;
    }
    printf("%d",ans);
    return 0;
}

 

21757번: 나누기

풀이

문제를 보자마자 부분합을 이용해야 할 것 같다는 생각이 확 들것이다. 구간을 잘 분할해서 수를 새어주면 된다.

먼저 S[i]를 1~i 까지의 모든 수의 합이라고 하자.

4개의 구간의 합이 모두 같아야 하므로 S[N] mod 4 = 0 이 아닌 것들은 바로 배제해준다.

 

이제 왼쪽에서 S[i]=S[N]/4 인 부분의 개수를 각 i 마다 구해주고 (i=0 부터 누적, 이를 A[i] 라 하자.)

오른쪽에서 S[N]-S[i]=S[N]/4 즉, S[i]=S[N]/4*3 인 부분들의 개수를 구해준다. (i=N 부터 누적, 이를 B[i] 라 하자.)

 

그러면 S[i]=S[N]/2인 모든 i에 대해 그 때의 가능한 방법의 개수는 A[i-1]*B[i+1]이다.

 

소스코드

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int sz=1e5+3;
ll A[sz],B[sz],S[sz];
int main(){
    int N;ll a;
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        scanf("%lld",&a);
        S[i]=S[i-1]+a;
    }
    if(S[N]%4){
        printf("0");
        return 0;
    }
    for(int i=1;i<=N;i++)A[i]=A[i-1]+(S[N]/4==S[i]?1:0);
    for(int i=N-1;i>0;i--)B[i]=B[i+1]+(S[N]/4*3==S[i]?1:0);
    ll ans=0;
    for(int i=2;i<N-1;i++)if(S[N]/2==S[i])ans+=A[i-1]*B[i+1];
    printf("%lld",ans);
    return 0;
}