cubalys   1년 전

1182번 부분집합의 합 문제는 풀었습니다.

다른 질문글 보니까 배열을 두 배열로 나누어서

각각 경우의 수를 찾은 다음

앞 배열에서 S가 나오는 경우의수 + 뒷 배열에서 S가 나오는 경우의 수 + 앞 뒤 배열에서 S가 나오는 경우의 수 를 구하라고 하시는데

앞 배열 에서 S가 나오는 경우의 수와 뒷 배열에서 S가 나오는 경우의 수는 구할 수 있겠는데

앞 뒤 배열의 부분집합을 하나씩 써서 나오는 경우의 수는 어떻게 구해야 하나요?

부분집합이 겹치지 않도록 그 합을 저장해야 할 것 같은데 감이 안오네요


소스는 1182번 부분집합의 합 소스 입니다.

baekjoon   1년 전

다음과 같이 생각할 수 있습니다.

먼저, 앞 배열을 A, 뒷 배열을 B라고 하고, 두 배열의 크기가 모두 N이라고 합니다. 그리고, 두 배열은 모두 오름차순으로 정렬되어 있습니다.

A 배열은 변수 i를 이용하고, B 배열은 변수 j를 사용합니다.

먼저, i=0, j=N-1입니다.

이 때, A[i] + B[j]의 값을 S와 비교해봅니다.

  • A[i] + B[j] < S 라면, 두 합은 커져야 합니다. 따라서, i++이 됩니다.
  • A[i] + B[j] > S 라면, 두 합은 작아져야 합니다. 따라서, j--이 되어야 합니다.
  • A[i] + B[j] == S 라면, 정답을 찾은 것 입니다. 이제 i++을 해서 다른 정답을 찾아봅니다.

cubalys   1년 전

아 값을 따로 저장해 둘 필요가 없군요 ㅜㅜ

감사합니다

cubalys   1년 전

음 그런데 그렇게 하면 A배열 인자 1개와 B배열 인자 1개를 쓴 경우만 구할 수 있지 않나요??

baekjoon   1년 전

아니요. 왜냐하면 A와 B 배열에는 합이 들어있기 때문입니다.

cubalys   1년 전

말씀하신 대로 코드 작성해 보았는데

어디서 틀렸는지를 모르겠습니다.

SUM 배열 출력해 봐도 잘 맞게 나오는 것 같은데

어디서 틀린건가요


cubalys   1년 전

아 배열 인자가 같은 경우도 있을 수 있으므로

Temp3 검사하는 반복문을 다음과 같이 수정했습니다

그래도 틀리네요 ㅜㅜ

august14   1년 전

같은 값이 여러개 있으면 어떻게 되는지 생각해보세요.

cubalys   1년 전

같은 값이 여러개 여도 값이 같은 동안은 계속 j-- 를 하니 상관 없지 않나요??

august14   1년 전

네 상관있습니다.

cubalys   1년 전

맞았습니다!

baekjoon님 august14님 감사합니다

초록글씨 보기 힘드네요 ㅜㅜ

kdhsong   1년 전

안녕하세요 ㅠㅠ 도저희몰라서 댓글남깁니다. 혹시 제소스에서 어떤부분이 틀렷는지 봐주실수있나요 ?ㅠㅠ진짜 한 30번은틀린거같아여



#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
     
using namespace std;
     
int arr[2][41];
int ind[2];
long long int part[2][2100000];
int N,S;
long long int cnt=0;
  
void dfs(int s,int e,int sum,int fr,bool flag){
    if(s == e+1)     return;
         
    if(flag){
        part[fr][ind[fr]++] = sum;
        if(sum == S)    cnt++;
    }
    dfs(s+1,e,sum+arr[fr][s+1],fr,true);
    dfs(s+1,e,sum,fr,false);
}
     
int main(){
    int j,i;
    scanf("%d %d",&N,&S);
    for(i = 0; i < N/2; i++) scanf("%d",&arr[0][i]);
    for(i = N/2; i < N; i++) scanf("%d",&arr[1][i]);
     
    long long int ret1,ret2,ret3 = 0;
    ind[0] = 0; ind[1] = 0;
    dfs(0-1, N/2-1, 0, 0, false); 
    ret1 = cnt; cnt=0;
             
    dfs(N/2-1, N-1, 0, 1, false);
    ret2 = cnt;
       
    sort(part[0], part[0] + ind[0]);
    sort(part[1], part[1] + ind[1]); 
     
    i = 0; j = ind[1]-1;
 
    while(i < ind[0] && j >= 0){
        long long int t = part[0][i]+part[1][j];
 
        if(S == t){
            long long int ci=1,cj=1;
 
            while(part[0][i] == part[0][i+1] && i < ind[0]){
                    i++;    
                   ci++;
            }
            while(part[1][j] == part[1][j-1] && j >= 0){
                    j--;    
                    cj++;
            }
            i++;j--;
            ret3 += ci*cj;              
        }
        else if(S < t)   j--;
        else i++;
    }
    // printf("%d %d %d",ret1,ret2,ret3);
     
    printf("%lld",ret1+ret2+ret3);
}


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