백준 1208, 부분 수열의 합

// https://www.acmicpc.net/problem/1208
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n, s;
    cin >> n >> s;

    int half = n/2;

    vector<int> first;
    vector<int> second;
    for(int i = 0; i < half; i++){
        int temp;
        cin >> temp;
        first.push_back(temp);
    }

    for(int i = 0; i < n-half; i++){
        int temp;
        cin >> temp;
        second.push_back(temp);
    }

    vector<int> fsum;
    vector<int> ssum;

    for(int i = 0; i < (1<<half); i++){
        int temp = 0;
        for(int j = 0; j < half; j++){
            if(i&(1<<j)){
                temp += first[j];
            }
        }
        fsum.push_back(temp);
    }

    for(int i = 0; i < (1<<(n-half)); i++){
        int temp = 0;
        for(int j = 0; j < n-half; j++){
            if(i&(1<<j)){
                temp += second[j];
            }
        }
        ssum.push_back(temp);
    }

    sort(fsum.begin(), fsum.end());
    sort(ssum.begin(), ssum.end());

    int l = 0; // first 체크
    int r = ssum.size() - 1; //second 체크
    long long cc = 0; // s갯수
    while(true){
        if(l >= fsum.size() || r < 0){
            break;
        }   

        int result = fsum[l] + ssum[r];
        if(result == s){
            long long lc = 1; // first 같은거 갯수
            long long rc = 1; // second 같은거 갯수
            for(int i = l + 1; i < fsum.size(); i++){
                if(fsum[i] != fsum[l]){
                    break;
                }
                lc++;
            }

            for(int i = r - 1; i >= 0; i--){
                if(ssum[i] != ssum[r]){
                    break;
                }
                rc++;
            }

            cc += (lc * rc);
            l = l + lc;
            r = r - rc;         
        }else if(result > s){
            // cout << "큼\n";
            r--;
        }else if(result < s){
            // cout << "작음\n";
            l++;
        }

    }

    if(s == 0){
        cc = cc-1;
    }

    cout << cc << "\n";

    return 0;
}

내 코드다. 

 

1) 오류가 난 이유: 아직 long long / int 범위 판단하는데 좀 어려운게 있는거같다. 이코드에서 Long long인 부분이 사실 왜 다 long long이여야하는지 잘모르겠다. 하려면 위에 1<<half할때두 했어야하는거같은데. 근데 여튼 범위상으로 생각하면 long long이 맞기는하다. 연습하면서 정리를 해야겠다.

 

2) 범위가 40개 숫자에 대해서 부분 수열을 구하는거라 시간초과가 나온다. 그래서 20/20으로 나눈다음 구하게 해야한다 -> 다른 비슷한 문제를 풀면서 연습을 해야한다

 

3) 비트마스크를 통해서 경우의 수를 구하면 좀 빠른감이 있다. 

 

4) 알고리즘 공부는 정말 중요한 것 같다. 생각보다 클라우드나 이런 관련 지식은 하기만 하면 금방 배우는건데, 알고리즘은 시간이 오래걸리는것같다.(어렸을떄부터 시작한 친구들을 이기기 가장 힘든 분야?)