[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 4회차 과제 에디토리얼

4회차 - 누적합, 투포인터

 

---

</11659> 구간 합 구하기 4

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

가장 기본적인 누적합 문제입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    vector<int> s(n + 1, 0);
    for (int i = 1; i < n + 1; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    while (m--) {
        int i, j;
        cin >> i >> j;
        cout << s[j] - s[i - 1] << '\n';
    }
}

 

---

</11660> 구간 합 구하기 5

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    vector<vector<int>> s(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] << '\n';
    }
}

누적합 구하는 법: 회색 사각형 = 빨간색 사각형 + 파란색 사각형 - 초록색 사각형 + 보라색 동그라미

답 구하는 법: 보라색 동그라미 (여러 원소들도 가능) = 회색 사각형 - 빨간색 사각형 - 파란색 사각형 + 초록색 사각형

 

---

</2003> 수들의 합 2

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

투포인터의 기본적인 문제입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    long long m;
    cin >> n >> m;

    vector<int> a(n + 1, 0);
    for (int i = 1; i < n + 1; i++) cin >> a[i];

    int s = 0;
    int e = 0;
    long long res = 0;
    int cnt = 0;
    while (s < n + 1 && e < n + 1) {
        if (res < m) {
            e++;
            res += a[e];
        } else if (res > m) {
            res -= a[s];
            s++;
        } else {
            cnt++;
            e++;
            res += a[e];
        }
    }

    cout << cnt << '\n';
}

 

---

</21921> 블로그

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

길이가 x일인 첫번째 구간을 먼저 구한 다음, 맨 앞 원소도 맨 뒤 원소도 한 칸씩 뒤로 밀면서 확인하면 되는 간단한 슬라이딩 윈도우 문제였습니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int sumt = 0;
    int s = 0;
    int e = 0;
    // 길이가 x일인 첫번째 구간
    while (e < x) {
        sumt += a[e];
        e++;
    }

    int maxt = sumt;
    int cnt = 1;

    while (e < n) {
        // 한칸씩 뒤로 이동하여 구간의 길이 유지
        sumt -= a[s];
        s++;
        sumt += a[e];
        e++;

        if (sumt > maxt) { // 최댓값이 갱신되면 cnt도 갱신
            maxt = sumt;
            cnt = 1;
        } else if (sumt == maxt) { // 아니라면 cnt만 1 증가
            cnt++;
        }
    }

    if (maxt == 0) cout << "SAD\n";
    else cout << maxt << '\n' << cnt << '\n';
}

 

---

</20922> 겹치는 건 싫어

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

연속 부분 수열에서 마지막 원소와 동일한 원소의 개수가 k보다 작으면 뒤의 원소 하나를 추가하고, k보다 크거나 같으면 마지막 원소와 동일한 원소까지의 원소들을 제거하고 원소를 다시 하나를 추가시키면 되는 투 포인터 문제였습니다.

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int cnt[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int s = 0;
    int e = 0;
    int maxt = 0;
    int cur = 0;

    while (e < n) {
        if (cnt[a[e]] < k) { // a[e]의 개수가 k보다 작다면
            cnt[a[e]]++;
            e++;
            cur++;
        } else { // a[e]의 개수가 k보다 크거나 같다면
            while (a[s] != a[e]) { // a[e]가 나올 때까지 a[s] 삭제 후 a 이동
                cnt[a[s]]--;
                s++;
                cur--;
            }
            cnt[a[s]]--;
            s++;
            cnt[a[e]]++;
            e++;
        }

        if (cur > maxt) maxt = cur;
    }

    cout << maxt << '\n';
}

 

---

</1806> 부분합

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

전형적인 누적 합 문제입니다. 연속된 수들의 합이 s보다 작으면 뒤쪽 원소를 하나 추가하고, s보다 크면 앞쪽 원소를 하나 제거하며 최소 길이를 계속 갱신해나가는 방식으로 문제를 해결하였습니다.

#include <iostream>
#include <vector>
using namespace std;

int MAX_INT = 100000;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int si = 0;
    int ei = 1;
    int sumt = a[0];
    int ans = MAX_INT;
    int cnt = 1;
    while (ei <= n) {
        if (sumt < s) { // sumt가 s보다 작으면 뒤쪽 원소 하나 추가
            sumt += a[ei];
            ei++;
            cnt++;
        } else { // 크면 갱신 후 앞쪽 원소 하나 제거
            ans = min(ans, cnt);
            sumt -= a[si];
            si++;
            cnt--;
        }
    }

    if (ans == MAX_INT) cout << 0 << '\n';
    else cout << ans << '\n';
}

 

---

</13900> 순서쌍의 곱의 합

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

단순하게 두 수의 쌍에 대해 곱을 구해서 더하면 $O(n^2)$의 시간 복잡도가 발생합니다. 하지만 최적화를 하면 $O(n)$의 시간 복잡도로 문제를 해결할 수 있습니다.

sum은 지금까지의 수들의 합이고 x는 현재 수라고 생각하면, sum과 x를 곱하면 현재 수와 이전 값들 사이의 곱의 합을 구할 수 있습니다. 그 후 sum에 x를 더해주고 반복을 계속하면 됩니다.

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int x;
    long long sum = 0;
    long long ans = 0;

    for (int i = 0; i < n; i++) {
        cin >> x;
        ans += sum * x;
        sum += x;
    }

    cout << ans << '\n';
}

 

---

</6137> 문자열 생성

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

왼쪽 포인터는 가장 왼쪽에서 시작하고 오른쪽 포인터는 가장 오른쪽에서 시작합니다. 둘 다 점점 가운데로 이동시키며, 계속 더 작은 문자를 택하며 정답을 구하면 되는 문제였습니다.

한가지 주의할 점은 왼쪽 문자와 오른쪽 문자가 같다면 같지 않을 때까지 계속 넘겨서 최종적으로 어디를 선택해야 최적일지 보고 선택해야 합니다.

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    string str;

    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        str += c;
    }

    int s = 0;
    int e = n - 1;
    string ans = "";

    while (s <= e) {
        if (str[s] < str[e]) { // 앞쪽 문자가 더 작으면
            ans += str[s];
            s++;
        } else if (str[s] > str[e]) { // 뒤쪽 문자가 더 작으면
            ans += str[e];
            e--;
        } else { // 앞쪽 문자와 뒤쪽 문자가 동일하면
            int tmps = s + 1;
            int tmpe = e - 1;
            while (tmps < tmpe && str[tmps] == str[tmpe]) { // 같으면 계속 이동
                tmps++;
                tmpe--;
            }
            if (str[tmps] < str[tmpe]) {
                ans += str[s];
                s++;
            } else {
                ans += str[e];
                e--;
            }
        }
    }

    int ansn = ans.size();
    for (int i = 0; i < n; i++) {
        if (i != 0 && i % 80 == 0) cout << '\n'; // 80글자마다 줄바꿈
        cout << ans[i];
    }
    cout << '\n';
}

 

---

</10986> 나머지 합

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

누적 합 문제의 약간 심화 버전이라고 생각하면 될 것 같습니다.

구간의 합이 m으로 나누어 떨어지는 경우를 봐야 하므로, 여기서는 누적 합 배열이 아닌 누적 합의 나머지 배열을 만드는 원리로 풀어야 합니다.

최종적으로 구해야 하는 것이 구간 합이 m으로 나누어 떨어지는 구간의 개수인데, 이를 구하려면 위의 방식으로 구한 구간 합 나머지 배열을 어떻게 활용 해야 할까요?

구간 합 나머지 배열을 통해 나머지가 i인 구간들의 개수를 구해두고, 나머지가 같은 구간끼리 빼면 구간 합이 m으로 나누어 떨어집니다. 저는 이를 cnt 배열로 뒀습니다.

좀 더 이해하기 쉽도록 예시를 들어보겠습니다. 원소가 5개 있다고 해봅시다. 4번째 원소까지의 합의 나머지가 3이고 2번째 원소까지의 합의 나머지도 3이면, 그 두 구간을 뺀 구간, 즉 3번째 원소부터 4번째 원소까지의 합의 나머지가 0이 됩니다. 즉, 나머지가 같은 구간에서 2개의 구간을 뽑으면 구간 합이 m으로 나누어 떨어지는 구간의 개수를 구할 수 있는 것입니다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // n: 배열의 크기, m: 나누는 값
    int n, m;
    cin >> n >> m;

    // a: 입력 배열
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // cnt[i]: 나머지가 i인 누적합이 등장한 횟수
    vector<int> cnt(m, 0);
    cnt[0] = 1;  // 누적합이 처음부터 나머지 0인 경우 처리

    int tmp = 0;
    for (int i = 0; i < n; i++) {
        tmp = (tmp + a[i]) % m;
        cnt[tmp]++;  // cnt 배열 갱신
    }

    long long ans = 0;
    for (int i = 0; i < m; i++) {
        ans += ((1LL * cnt[i] * (cnt[i] - 1)) / 2);  // 같은 나머지를 가진 것들끼리 조합 계산
    }

    cout << ans << '\n';
}

아래의 코드는 ans를 구하는 과정을 약간 더 최적화한 코드입니다. 128ms에서 112ms로 시간을 약간 줄일 수 있지만… 굳이 하실 필요는 없긴 합니다… ㅎㅎ

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // n: 배열의 크기, m: 나누는 값
    int n, m;
    cin >> n >> m;

    // a: 입력 배열
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    // cnt[i]: 나머지가 i인 누적합이 등장한 횟수
    vector<int> cnt(m, 0);
    cnt[0] = 1;  // 누적합이 처음부터 나머지 0인 경우 처리

    int tmp = 0;
    long long ans = 0;  // 정수 범위 초과 방지를 위해 long long 사용

    for (int i = 0; i < n; i++) {
        tmp = (tmp + a[i]) % m;
        ans += cnt[tmp];  // 현재 나머지가 같은 개수만큼 정답에 추가
        cnt[tmp]++;       // cnt 배열 갱신
    }

    cout << ans << '\n';
}