[코드포스 Practice22] A. Lesha and array splitting

주어진 배열을 sub배열로 나누는데 sub배열의 합이 0이 되면 안 된다. 전체 0인 경우는 NO를 출력하면 된다는 걸 알겠는데 그 다음을 어떻게 해야할지 몰라서 해맸다. 이걸 하나씩 출력하려고 했는데 그럼 중간에 0이 있으면 또 단위를 크게 해서 묶어줘야 하고. 0이 아니게 묶어주는 기준을 못 찾아서 결국 못 풀었다.

 

이 문제는 일단 전체 합이 0이 아니면 범위를 전체로 해서 구할 수 있다. 다음으로 전체 합이 0인 경우가 문제인데, 이 경우는 두 개의 구간을 사용하면 해결할 수 있다. 임의의 좌표 i를 기준으로 오른쪽의 합이 k라고 하면 왼쪽은 -k일 것이다. (전체의 합이 0이어야 하므로) 그래서 왼쪽에서 합이 0이 아닌 지점을 찾아서 그 지점을 기준으로 왼쪽, 오른쪽을 나누면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);

    vector<int> v(n);
    int sum = 0;
    bool is_zero = true;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &v[i]);
        sum += v[i];
        if (v[i] != 0)
            is_zero = false;
    }

    if (is_zero)
    {
        printf("NO\n");
        return 0;
    }

    printf("YES\n");
    if (sum != 0)
    {
        printf("1\n");
        printf("1 %d", n);
        return 0;
    }

    int index = 0;
    for (int i = 0; i < n; i++)
    {
        if (v[i] != 0)
        {
            index = i;
            break;
        }
    }
    printf("2\n");
    printf("1 %d\n", index + 1);
    printf("%d %d", index + 2, n);
    
    return 0;
}

 

 

이건 내코드

 

아래는 북님 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);

    vector<int> psum(n + 1);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &psum[i]);
        psum[i] += psum[i-1];
    }

    if (psum[n] != 0)
    {
        printf("YES\n1\n1 %d", n);
        return 0;
    }

    for (int i = 1; i <= n; i++)
    {
        if (psum[i] != 0)
        {
            printf("YES\n2\n%d %d\n%d %d\n", 1, i, i+1, n);
            return 0;
        }
    }
    
    printf("NO\n");
    return 0;
}

 

(복붙 아니고 직접 친 거임)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);

    vector<int> psum(n + 1);

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &psum[i]);
        psum[i] += psum[i-1];
    }

    if (psum[n] != 0)
    {
        printf("YES\n1\n1 %d", n);
        return 0;
    }

    for (int i = 1; i <= n; i++)
    {
        if (psum[i] != 0)
        {
            printf("YES\n2\n%d %d\n%d %d\n", 1, i, i+1, n);
            return 0;
        }
    }
    
    printf("NO\n");
    return 0;
}

 

오! 합을 구하는 부분을 부분합으로 미리 계산해놨다. 생각해보니 기존 배열이 필요 없었네. psum[n]이 전체 합이 될 거거라 psum[n]이 0이 아니면 전체를 답으로 삼고 아니라면 배열 전체를 다 확인하면서 psum 배열이 0이 아닌 값을 찾는다. 찾지 못한다면 이 때는 배열이 전부 0일 때 이므로 NO를 출력한다.