C - 17610 양팔저울

 

https://www.acmicpc.net/problem/17610

여러개의 무게가 다른 추가 주어졌을때 양팔저울을 한번 써서 만들지 못하는 무게가 몇가지있는지 찾는 문제이다.

 

모든 경우를 아우를 수 있는 경우를 생각하다가 대략 형태는 잡을 수 있었다.

 

nC0 +- nC1~nCn-0

nC1 +- nC1~nCn-1

...

nCr +- nC1 ~ nCn-r

이런식으로 x개를 뽑아서 뽑은 x개를 제외한 나머지에서 다시 1개~n-x개를 뽑으며 모든 수를 아까 x개 뽑은 수에 +- 해보면

주어진 추로 만들 수 있는 모든 경우의 수를 아우를 수 있다.

 

r개를 뽑아서 조합했을때 / 뽑은것을 제외한 나머지로 조합하는식으로 구현했다.

void find_nCr() {
    for(int i=0; i<=cnt; i++) {
        dfs(0, 0, i, 0); //nCi
    }
}

void dfs(int idx, int select, int R, int sum) {
    if(select == R) {
        std = sum;
        for(int i=1; i<=cnt-R; i++)
            tmp_dfs(0,0,i, 0);
        return;
    }
    for(int i=idx; i<cnt; i++) {
        if(visited[i] == 0) {
            visited[i] = 1;
            dfs(i, select+1, R, sum + num[i]);
            visited[i] = 0;
        }
    }
}

void tmp_dfs(int idx, int select, int R, int sum) {
    if(select == R) {
        // printf("%d %d :", std, sum);
        // printf("%d %d\n", std+sum, abs(std-sum));
        arr[abs(std-sum)] = 1;
        arr[std+sum] = 1;
        return;
    }
    for(int i=idx; i<cnt; i++) {
        if(visited[i] == 0) {
            visited[i] = 1;
            tmp_dfs(i, select+1, R, sum + num[i]);
            visited[i] = 0;
        }
    }
}

 

문제의 예제로 주어진 1, 2, 7을 테스트해볼 경우 아래와 같은 결과를 낸다.

조합1 조합2 : 조합1 + 조합2 abs( 조합1 - 조합2 ) 와 같은 출력이다.

 

결과를 보면 절반을 기점으로 중복된 결과를 만드는것을 알 수 있다.

따라서 중복 제거로 처음 조합을 절반까지만 뽑게 만들려면 (nCn-r 에서 r이 n/2이 넘으면)

아래 코드처럼 i를 cnt까지 뽑지말고 cnt/2까지 뽑으면된다.

void find_nCr() {
    for(int i=0; i<=cnt/2; i++) {
        dfs(0, 0, i, 0); //nCi
    }
}

 

이럴 경우 결과는 아래와 같이 중복되는 부분을 줄일 수 있다

 

이제 1~nCn인 수를 모두 구할 수 있는지 확인하고 구하지 못한 경우의 수를 구해 출력해주면 된다.

void answer() {
    //printf("answer : ");
    int find_case = 0;
    for(int i=1; i<=max; i++) {
        if(arr[i] == 0) find_case++; //printf("%d ", i);
    }
    printf("%d\n", find_case);
}

 

 

전체 코드

https://github.com/shirohebiui/BAEKJOON/blob/988b089f0fed88c35091cd3af0c8dbd73aa0d730/%23Bruteforce/S/17610(S1).c