글 읽기 - 어느 부분이 잘못된 로직인지 모르겠습니다. 조언 부탁드립니다.

suhinwebtoon 4년 전 0

어느 부분이 잘못된 로직인지 모르겠습니다.

시간초과나 메모리초과가 나오지는 않고, 틀렸습니다.라고만 나오네요.

조언 부탁드립니다.

#include<iostream>
#include <vector>
#include <algorithm>
#define MAX_SIZE 40

using namespace std;

long long number[MAX_SIZE];

int main()
{
    int answer=0;
    int N, S;
    cin >> N >> S;
	
    for(int index = 0; index < N; ++index)
        cin >> number[index];
    
    vector<long long> first_half;
    vector<long long> last_half;
    int half = N/2;
    
    for(int choose = 0; choose < (1 << half); ++choose)
     {
         long long sum = 0;
         for(int index = 0; index < half; ++index)
         {
             if(choose & (1 << index))
                 sum += number[index];
         }
         first_half.push_back(sum);
     }
   	 for(int choose = 0; choose < (1 << N-half); ++choose)
     {
         long long sum = 0;
         for(int index = 0; index < N-half; ++index)
         {
             if(choose & (1 << index))
                 sum += number[index+half];
         }
         last_half.push_back(sum);
     }
    
    sort(first_half.begin(), first_half.end());
    sort(last_half.begin(), last_half.end());
    
    for(int index = 0; index <first_half.size(); ++index)
    {
        int high = upper_bound(last_half.begin(), last_half.end(), S-first_half[index]) - last_half.begin();
        int low = lower_bound(last_half.begin(), last_half.end(), S-first_half[index]) - last_half.begin();

        answer += (high - low);
    }
    if(S == 0)
        answer--;
    cout << answer << endl;
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어느 부분이 잘못된 로직인지 모르겠습니다. 조언 부탁드립니다.

suhinwebtoon 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말