📘 문제

문제링크 : https://www.acmicpc.net/problem/1450 (단계별로 풀어보기 : 투 포인터)

📝 문제 풀이

해당 문제를 재귀로 처음 접근해서 재귀로만 풀려하니 문제가 많이 발생했다. 조금 찾아보고 방법을 가져왔다. 일단 큰 알고리즘은 주어진 배열을 반으로 나누어 front_part, back_part로 구분하자. 그럼 front_part에 있는 수들로 만들 수 있는 합들을 구하고, back_part에 있는 수들로 만들 수 있는 합들을 구한다. 그렇게 되면 만약 배열 1,2,3,4 가 있다면 1,2가 front, 3,4가 back 파트가 되고 각각 (0,1,2,3), (0,3,4,7) 의 합들을 구할 수 있다. 그 다음 한쪽만 정렬하여 정렬하지 않은 부분에서 한개씩 정렬한 부분과 비교하여 문제의 답에 적합한지 판단한다. 이것이 큰 알고리즘이고, 합들을 계산하려면 재귀로 모든 수에 대해서 그 수가 더해지는 경우와 더해지지 않는 경우로 가지치기 될 것이고 모든 합들을 계산할 수 있다. 마지막으로 정렬하지 않은 부분에서 정렬한 부분을 비교하며 정답의 개수를 셀 때 for문을 돌리지 않고 upper_bound를 사용하여 구해주었다. upper_bound와 lower_bound를 알고 있다면 몇몇 문제에서 코드를 더 간결하게 짤 수 있을 것 같다.

✏️ 알고리즘 스케치

💻 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

void makeSums(int start, int end, vector<ll>& arr, vector<ll>& vec, ll sum){
    if(start>end){
        vec.push_back(sum);
    }
    else{
        makeSums(start+1, end, arr, vec, sum);
        makeSums(start+1, end, arr, vec, sum + arr[start]);
    }
}

int main()
{
    int N, C;
    cin >> N >> C;

    vector<ll> arr;
    arr.resize(N,0);
    for(int i=0; i<N; i++)
        cin >> arr[i];

    vector<ll> leftSums, rightSums;
    makeSums(0,N/2-1,arr,leftSums,0);
    makeSums(N/2,N-1,arr,rightSums,0);

    sort(rightSums.begin(), rightSums.end());

    int leftSumsSize = leftSums.size(), sol = 0;
    for(int i=0; i<leftSumsSize; i++){
        ll restC = C - leftSums[i];
        sol += upper_bound(rightSums.begin(),rightSums.end(),restC) - rightSums.begin();
    }
    cout << sol;

    return 0;
}