[C/C++] 프로젝트 오일러 #105 Special Subset Sums: Testing(정렬)

Project Euler #105: Special Subset Sums: Testing 문제는 집합과 관련된 수학적 속성을 탐구하며, 특정 조건을 만족하는 집합을 찾는 문제입니다. 문제의 난이도는 꽤 높은 45%로 되어 있습니다.  문제를 풀이하는 데 필요한 개념과 단계는 다음과 같습니다:

주어진 집합 S는 다음 두 가지 조건을 만족해야 합니다:
1. 조건 A: 두 개의 서로 다른 비어 있지 않은 부분 집합 와 에 대해, 다음이 성립해야 합니다:
• \(  A \cap B = \emptyset \) (즉, A 와 B 는 서로소입니다.)
• A 와 B 에 대해 \(  |A| > |B|  \) 라면 \(  \text{sum}(A) > \text{sum}(B) \) 여야 합니다.
2. 조건 B: 모든 부분 집합 쌍 A 와 B (위와 동일하게 서로소 조건을 만족해야 함)에 대해 \(  \text{sum}(A) \neq \text{sum}(B) \) 여야 합니다.

이 문제는 위 조건들을 만족하는 집합을 판별하는 것이 핵심입니다. 주어진 집합 S 에 대해 모든 조건을 만족하는지 확인한 뒤, 조건을 만족하는 집합의 합계를 구합니다.

문제에서 예시로 제공하는 집합 \(  S = \{81, 88, 75, 42, 87, 84, 86, 65\} \) 에 대해 조건을 만족하는지 확인하는 과정을 생각해 봅시다.
1. 가능한 부분 집합 조합을 생성합니다.
2. 각 부분 집합 쌍에 대해 조건 A와 조건 B를 모두 확인합니다.
3. 조건을 만족하는 S 의 총합을 계산합니다.

• 조건 A는 \(  |A| > |B| \) 의 경우에만 확인하면 되므로, 부분 집합 크기에 따라 우선순위를 둬서 검사할 수 있습니다.
• 조건 B는 합계가 중복되지 않도록 트리 구조 또는 해시를 이용해 빠르게 확인할 수 있습니다.
• 동적 프로그래밍 또는 정렬을 통해 계산을 최적화할 수 있습니다.

set and subset

 

제가 작성한 코드를 여기에 소개합니다.

//------------------------------------------------
//    Project Euler #105 - Special Subset Sums: Testing
//        - by Aubrey Choi
//        - created at 2015-04-13
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define    FN "p105_sets.txt"

int CheckAndSum(int sss[], int n)
{
    int cb[4096];
    int suma = sss[0], sumb = 0;
    for( int r = 1 ; r <= n/2 ; r++ )
    {
        suma += sss[r];
        sumb += sss[n-r];
        if( suma <= sumb ) return 0;
    }

    cb[0] = 0;
    for( int i = 0 ; i < n ; i++ )
    {
        for( int j = 0 ; j < (1<<i) ; j++ )
        {
            int c = cb[(1<<i)+j] = cb[j]+sss[i];
            for( int k = 1 ; k < (1<<i) ; k++ )
                if( c == cb[k] ) return 0;
        }
    }

    return cb[(1<<n)-1];
}

int main()
{
    FILE *fi = fopen(FN, "r");
    int sum = 0;

    char str[128];
    while( fgets(str, 128, fi) )
    {
        int n = 0;
        int sss[20];
        for( char *tok=strtok(str, ", \r\n") ; tok ; tok=strtok(0, ", \r\n"))
        {
            int c = atoi(tok);
            int last = n++;
            while( last > 0 )
            {
                if( sss[last-1] < c ) break;
                sss[last] = sss[last-1];
                last--;
            }
            sss[last] = c;
        }
        sum += CheckAndSum(sss, n);
    }
    fclose(fi);
    printf("ans = %d\n", sum);
}

 

1. 조건 A 체크:
• S 를 내림차순으로 정렬.
• 작은 부분 집합부터 점진적으로 합계를 계산해 조건 suma > sumb 를 검증.
2. 조건 B 체크:
• 부분 집합 합계를 비트마스크를 사용하여 계산.
• 각 합계가 중복되는 경우, 조건 위반으로 판단.
3. 효율성 확보:
• 비트마스크를 사용해 모든 부분 집합 합계를 효율적으로 생성 및 비교.
• 정렬된 S를 기반으로 조건 A를 빠르게 확인.

1. CheckAndSum 함수

int CheckAndSum(int sss[], int n)
{
    int cb[4096];
    int suma = sss[0], sumb = 0;

    // 조건 A: 작은 부분 집합부터 점진적으로 합 비교
    for( int r = 1 ; r <= n/2 ; r++ )
    {
        suma += sss[r];
        sumb += sss[n-r];
        if( suma <= sumb ) return 0;
    }

    // 조건 B: 비트마스크를 사용해 모든 부분 집합 합계 체크
    cb[0] = 0;
    for( int i = 0 ; i < n ; i++ )
    {
        for( int j = 0 ; j < (1<<i) ; j++ )
        {
            int c = cb[(1<<i)+j] = cb[j]+sss[i];
            for( int k = 1 ; k < (1<<i) ; k++ )
                if( c == cb[k] ) return 0;
        }
    }

    return cb[(1<<n)-1];
}

첫 번째 for 루프:
• 조건 A를 검증.
• suma 는 가장 큰 값부터 r 개의 합, sumb 는 가장 작은 값부터 r 개의 합을 계산하여 비교.
• 만약 \(  suma \leq sumb \) 라면 조건 위반이므로 0 반환.
두 번째 for 루프:
• 조건 B를 검증.
• 비트마스크를 활용하여 모든 부분 집합 합계를 배열 cb에 저장.
• 중복된 합계가 발견되면 조건 위반으로 0 반환.
리턴 값:
• 조건을 모두 만족하는 경우, 전체 합계 반환.

2. main 함수

int main()
{
    FILE *fi = fopen(FN, "r");
    int sum = 0;

    char str[128];
    while( fgets(str, 128, fi) )
    {
        int n = 0;
        int sss[20];
        for( char *tok=strtok(str, ", \r\n") ; tok ; tok=strtok(0, ", \r\n"))
        {
            int c = atoi(tok);
            int last = n++;
            while( last > 0 )
            {
                if( sss[last-1] < c ) break;
                sss[last] = sss[last-1];
                last--;
            }
            sss[last] = c;
        }
        sum += CheckAndSum(sss, n);
    }
    fclose(fi);
    printf("ans = %d\n", sum);
}

파일 입력 처리:
• 파일 p105_sets.txt에서 한 줄씩 읽고, 숫자를 파싱하여 배열 sss에 저장.
• 내림차순으로 삽입 정렬을 통해 조건 A를 확인하기 쉽게 준비.
조건 검증:
• 각 집합에 대해 CheckAndSum을 호출하여 조건 A와 B를 확인.
• 조건을 만족하면 합계를 sum에 추가.
출력:
• 최종적으로 조건을 만족하는 집합들의 합계를 출력.

기술적 기법

1. 비트마스크 활용:
• n개의 원소에 대해 \(2^n\) 개의 부분 집합을 효율적으로 생성하고 비교.
2. 정렬:
• 조건 A 확인을 위한 내림차순 정렬로 빠른 검증.
3. 삽입 정렬:
• 입력 파일에서 정렬된 형태로 데이터를 효율적으로 저장.