나누기( BOJ 21757 )

문제: https://www.acmicpc.net/problem/21757

21757번: 나누기

 

문제 파악하기

N개의 숫자를 정확히 4등분으로 나누는 문제입니다. 나누어진 부분의 합이 모두 동일해야 한다는 조건이 있는데 이 조건에 초점을 맞추면 문제를 해결할 수 있습니다. 4개의 부분합이 모두 동일하기 위해서는 각각의 부분합은 (전체 N개 숫자의 누적합)/4의 값을 만족합니다. 이는 단순하게 생각하면 도출할 수 있는 결론입니다. 이를 통해 우리는 나올 수 있는 경우를 나눠 문제를 해결해보겠습니다.

 

문제 해결하기

전체 누적합에 따라 나올 수 있는 경우의 수는 총 3가지 입니다.

(1) 전체 누적합이 0인 경우

(2) 전체 누적합이 4의 배수가 아닌 경우

(3) 전체 누적합이 4의 배수인 경우

 

첫 번째, 전체 누적합이 0인 경우입니다. 이 경우, 전체 누적합 중 0의 개수를 통해 간단하게 구할 수 있습니다. 누적합 중 0이 나오는 숫자를 zero라고 한다면, 4등분으로 나눌 수 있는 모든 경우의 수는 _(zero-1)C₃으로 나타낼 수 있습니다.

 

두 번째, 전체 누적합이 4의 배수가 아닌 경우입니다. 전체 누적합이 4의 배수가 아닌 경우에는 정확하게 4등분으로 나눌 수 없습니다. 이 경우, 나올 수 있는 경우의 수는 0입니다.

 

마지막으로, 전체 누적합이 4의 배수인 경우입니다. 이 경우에는 누적합을 하나씩 확인하면서 전체 경우의 수를 파악할 수 있습니다. 우선 (전체 누적합)/4의 값을 K라고 가정해봅시다. 그럼 나눠진 4개의 부분합은 항상 K로 표현할 수 있으며, 이를 누적합으로 나타내면 K의 배수로 표현됩니다. 첫 번째 부분합은 K, 두 번째는 K*2, 세 번째는 K*3, 마지막은 K*4로 나타낼 수 있으며, 우리는 누적합만 보더라도 구간으로 나눌 수 있는지 없는지 알 수 있습니다.

 

예를 들어 { 4 -1 2 1 -3 1 2 2 1 3 } 를 보면 다음과 같이 누적합을 만들 수 있습니다.

4

3

5

6

3

4

6

8

9

12

이렇게 만들어진 누적합을 잘 보면 현재 이 수열에서 K의 값은 3이라는 걸 알 수 있습니다. 그리고 3*2, 3*3, 3*4의 값이 적혀있는걸 볼 수 있는데 이 모든 숫자들은 현재 구간을 나눌 수 있다는 의미입니다. 3*1인 경우에는 첫 번째 구간, 3*2인 경우에는 두 번째 구간으로, 3*3인 경우에는 세 번째 구간으로 나눌 수 있다는 걸 의미합니다.

 

따라서, 우리는 1부터 (N-1)까지의 누적합을 하나씩 탐색해보면서 현재 누적합이 K, K*2, K*3이라면 해당 구간을 만들 수 있는 모든 경우의 수를 구하면 됩니다. 여기서 해당 구간을 만드는 경우의 수는 1차원 배열(dp)을 사용해서 나타낼 수 있습니다. 만약 현재 누적합이 K*t이고, dp[t]가 t번째 구간까지 나눌 수 있는 경우의 수라고 하면, dp[t] = dp[t] + dp[t-1] 의 값을 저장하면 됩니다. 현재까지 t번째 구간을 나눌 수 있는 경우의 수는 (t-1)번째 구간까지 만들 수 있는 경우의 수와 현재 t번째 구간을 나눌 수 있는 경우의 수를 더하면 구할 수 있기 때문입니다.

 

이렇게 점화식을 구할 때, 명심할 점은 K*4의 경우는 제외해야 한다는 점입니다. K*4는 항상 가장 마지막 숫자만이 될 수 있으며, 그 전에 나온 숫자의 경우에는 무시하고 탐색해야 정확한 값을 얻을 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

소스코드는 메모이제이션 버전과 위의 풀이 버전을 올립니다.

// 
#include <stdio.h>
#include <string.h>
#define NMAX 100010
 
int N;
int inp[NMAX], sum[NMAX];
 
long long int val, ret;
long long int dp[NMAX][4];
 
 
long long int sv(int idx, int cnt) {
    // 메모이제이션
    if(dp[idx][cnt] >= 0) return dp[idx][cnt];
 
    // 종료 시점
    if(idx > N) return dp[idx][cnt] = 0;
    else if(cnt == 3) {
        if(sum[N] - sum[idx-1] == val) return dp[idx][cnt] = 1;
        else return dp[idx][cnt] = 0;
    }
 
    // 탐색
    long long ret = 0;
    for(int nxt=idx;nxt<=N;nxt++) {
        long long int tmp = sum[nxt] - sum[idx-1];
 
         // 첫 번째 수열 값과 같은 경우
        if(tmp == val) ret += sv(nxt+1, cnt+1);
    }
 
    return dp[idx][cnt] = ret;
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i]);
 
        sum[i] = sum[i-1]+inp[i];
    }
 
        // 나올 수 없는 경우
        if(sum[N]%4>0) ret = 0;
        else {
            // 누적합이 0인 경우
            if(!sum[N]) {
                long long int zero=0;
                for(int i=1;i<=N;i++) zero += (!sum[i]);
 
                ret = (zero-1)*(zero-2)*(zero-3)/6;
            }
            // DP
            else {
                val = sum[N]/4;
                memset(dp, -1, sizeof(dp));
                for(int i=1;i<=N;i++) {
                    if(sum[i] == val) ret += sv(i+1, 1);
                }
            }
        }
 
    // 출력
    printf("%lld", ret);
}

 

// 풀이법
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100010
 
int N;
int inp[NMAX], sum[NMAX];
 
int val;
long long int ret;
long long int dp[5];
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d", &inp[i]);
 
        sum[i] = sum[i-1]+inp[i];
    }
 
        // 나올 수 없는 경우
        if(sum[N]%4>0) ret = 0;
        else {
            // 누적합이 0인 경우
            if(!sum[N]) {
                long long int zero=0;
                for(int i=1;i<=N;i++) zero += (!sum[i]);
 
                ret = (zero-1)*(zero-2)*(zero -3)/6;
            }
 
            // DP
            else {
                dp[0] = 1;
                val = sum[N]/4;
 
                for(int i=1;i<=N;i++) {
                    int t = sum[i]/val;
                    if(sum[i]%val!=0 or t<1 or t>4) continue;
 
                    dp[t] += dp[t-1];
                }
 
                ret = dp[4];
            }
        }
 
    // 출력
    printf("%lld", ret);
}
/*
16
0 0 0 0 0 3 0 1 2 0 0 0 2 1 3 0
ans:8
*/

후기

항상 부분합이 ( 전체 누적합/4 )라는 점을 도출하는데 시간이 걸린 문제입니다. 처음에는 메모이제이션으로 해결했는데 다른 사람들의 소스코드를 보고 영감을 얻어 위의 풀이법을 만들게 되었습니다. 이 문제는 다이나믹 프로그래밍 부분 보다는 누적합의 개념을 활용하는 부분이 더 많다고 생각하기에 누적합 문제로 추천드립니다.