[중급 알고리즘] Brute Force 확장

💚 2003 수들의 합 2

총 방법의 수 3가지

- $O(N^3)$: i 정하기, j 정하기, i ~ j 구간합 구하기

- $O(N^2)$: i 정하기, j 정하기, 합은 중복 합 활용

- $O(N)$: 모든 배열값이 양수라는 점 활용

 

i = a, j = b의 합이 M보다 작았고 i = a, j = b + 1의 합이 M보다 큰 경우를 생각해보자.

식으로 나타내면 다음과 같다.

$A[a] + A[a + 1] + ... + A[b] < m$

$A[a] + A[a + 1] + ... + A[b + 1] > m$

이 경우 j를 계속 증가시키는 것은 의미가 없기 때문에 i를 증가시켜야 한다.

그런데 i = a + 1, a + 1 $<=$ b인 경우에서 합이 M이 되는 경우는 있을 수가 없다.

A[a + 1] + ... + A[b] == M이라면, A[a] + ...A[b] > M이기 때문에 처음의 전제와 다르고 모수닝 발생한다.

따라서 이런 경우는 i만 증가시키면 된다.

#include <iostream>

using namespace std;
int a[100001];
int main() {
    int n;
    int s;
    cin >> n >> s;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    
    int left = 0, right = 0;
    int sum = a[0];
    int ans = 0;
    while(left <= right && right < n) {
        if(sum < s) {
            right += 1;
            sum += a[right];
        }
        else if(sum == s) {
            ans += 1;
            right += 1;
            sum += a[right];
        }
        else {
            sum -= a[left];
            left++;
            // 합 범위가 1개인 경우에서 left가 진행되는 경우 처리
            // 원소가 하나인 상태에서 해당 원소가 s보다 큰 경우에는 다음 원소로 넘어간다.
            if(left > right && left < n) {
                right = left;
                sum = a[left];
            }
        }
    }
    
    cout << ans << '\n';
}

💚 1644 소수의 연속합

위 문제와 같지만 소수를 구해서 답을 구해야 하는 문제

소수는 에라토스테네스의 체를 활용한다.

#include <iostream>
#include <vector>

using namespace std;
int a[100001];
int main() {
    int n;
    cin >> n;
    vector<bool> c(n + 1);
    vector<int> p;
    
    // 에라토스테네스의 체
    for(int i = 2;i <= n;i++) {
        if(c[i] == false) {
            // 소수 모으기
            p.push_back(i);
            for(int j = i * 2;j <= n;j += i) {
                c[j] = true;
            }
        }
    }
    
    int left = 0, right = 0;
    int sum = p.empty() ? 0 : p[0];
    int ans = 0;
    // loop 내 동작 방식: 합 판단 -> 인덱스 조정과 다음 합으로 세팅
    while(left <= right && right < p.size()) {
        if(sum <= n) {
            if(sum == n) {
                ans += 1;
            }
            right++;
            if(right < p.size()) {
                sum += p[right];
            }
        }
        else {
            sum -= p[left++];
        }
    }
    
    cout << ans << '\n';
    return 0;
}

중간에서 만나기

분할 정복(나눠지고 합쳐진다.)이랑 헷갈리면 안된다.

문제를 절반으로 나눠서

양쪽 절반에서 모든 경우를 다 해보는 방법이다.

탐색의 크기가 많이 줄어든다.

문제의 크기가 N인 경우에 $2^N$에서 M = $\frac{N}{2}$라고 했을 때 $2^M + 2^M$으로 줄어든다.

 

💚1208 부분수열의 합2 💥✨

모든 부분 수열을 다 만들어볼 경우에 경우의 수가 지나치게 크다.

절반으로 배열을 나눠서 각각 모든 가능한 부분수열을 만들어본다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
    int n, s;
    cin >> n >> s;
    vector<int> a(n);
    
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    
    int m = n / 2;
    n = n - m;

    
    vector<int> first(1 << n);
    for(int i = 0;i < (1 << n);i++) {
        for(int k = 0;k < n;k++) {
            if(i & (1 << k)) {
                first[i] += a[k];
            }
        }
    }
    vector<int> second(1 << m);
    for(int i = 0;i < (1 << m);i++) {
        for(int k = 0;k < m;k++) {
            if(i & (1 << k)) {
                second[i] += a[k + n];
            }
        }
    }
    
    sort(first.begin(), first.end());
    sort(second.begin(), second.end());
    reverse(second.begin(), second.end());
    
    n = (1 << n);
    m = (1 << m);
    
    int i = 0;
    int j = 0;
    
    long long ans = 0;
    while(i < n && j < m) {
        if(first[i] + second[j] == s){
            // first[i]와 동일한 합을 지닌 부분배열의 개수
            long long c1 = 1;
            // first[j]와 동일한 합을 지닌 부분배열의 개수
            long long c2 = 1;
            
            i += 1;
            j += 1;
            // 같은 합을 지닌 부분배열
            while(i < n && first[i] == first[i - 1]) {
                c1 += 1;
                i += 1;
            }
            
            while(j < m && second[j] == second[j - 1]){
                c2 += 1;
                j += 1;
            }

            ans += c1 * c2;
        }
        else if(first[i] + second[j] < s) {
            i += 1;
        }
        else {
            j += 1;
        }
    }
    // s가 0인 경우도 고려
    // 크기가 양수여야 하기 때문
    if(s == 0) ans -= 1;
    cout << ans << '\n';
    return 0;
}

💚 2143 두 배열의 합

equal_range: first는 lower_bound, second는 upper_bound로 리턴

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t, n, m;
    cin >> t;
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    
    cin >> m;
    vector<int> b(m);
    for(int i = 0;i < m;i++) {
        cin >> b[i];
    }
    // 부배열의 원소 각각 만들기
    vector<int> x;
    for(int i = 0;i < n;i++) {
        int sum = 0;
        for(int j = i;j < n;j++) {
            sum += a[j];
            x.push_back(sum);
        }
    }
    
    vector<int> y;
    for(int i = 0;i < m;i++) {
        int sum = 0;
        for(int j = i;j < m;j++) {
            sum += b[j];
            y.push_back(sum);
        }
    }
    
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    
    long long ans = 0;
    for(int i = 0; i < x.size();i++ ){
        auto p = equal_range(y.begin(), y.end(), t - x[i]);
        ans += p.second - p.first;
    }
    
    cout << ans << '\n';
    return 0;
    
    
}

💚 7453 합이 0인 네 정수

그냥 A, B, C, D 경우를 무작정 모두 구하면 $N^4$이라는 시간 복잡도를 가진다. 

하지만 A[a] + B[b] = -(C[c] + D[d])로 구하면 각각 $N^2$가지로 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    for(int i = 0;i < n;i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    
    vector<int> first, second;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++){
            first.push_back(a[i] + b[j]);
            second.push_back(c[i] + d[j]);
        }
    }
    
    sort(second.begin(), second.end());
    long long ans = 0;
    for(int num : first) {
        auto range = equal_range(second.begin(), second.end(), -num);
        ans += range.second - range.first;
    }
    cout << ans << endl;
    return 0;
}