Brute Force: 조합

N개의 수가 주어졌을 때. 그중에서 K개를 뽑는 경우 혹은 그 수를 구할 때, 다음과 같은 방법을 이용해 구할 수 있다.

 

순서는 조합에서 의미가 없으므로, 크게

  i를 사용하는 경우, 사용하지 않는 경우

혹은 다른 말로

  i번째 수로 m을 사용하는 경우, 사용하지 않는 경우로 나누어 생각할 수 있다.

 

    1. 1~N까지 N개의 수 중에서, K개를 뽑는 경우

    2. 입력된 N개의 수 중에서. K개를 뽑는 경우

  두 가지 경우에 대해 다뤄보겠다.

코드_1

#include <cstdio>
int N,K, cnt=0;
void Combination (int c[], int i, int n) {
    if(i<=K && n<=N) {
        c[i] = n; // i번째 수를 n으로 한다.
        if(i == K) {
            for(int j=1;j<=K;++j)
                printf("%d ",c[j]);
            printf("\n");
            // 여기서 return하면 n을 넣지 않는 경우 도달 불가
            Combination(c,i,n+1); // i를 선택하지 않는 경우 호출하고
            cnt++;
            return; // 반환
        }
        Combination(c,i+1,n+1); // i를 선택하는 경우
        Combination(c,i,n+1); // i를 선택하지 않는 경우
    }
}

int main () {
    scanf("%d%d",&N,&K);
    int c[N+1];
    Combination(c,1,1);
    printf("cnt: %d",cnt);
}

1~N까지 연속된 수인 경우 nCk를 계산할 수 있다.

 

코드_2

#include <cstdio>
int N,K, cnt=0;
void Combination (int in[], int c[], int i, int n) {
    if(i<=K && n<=N) {
        c[i] = in[n]; // n 대신 사용자 입력 사용
        if(i == K) {
            for(int j=1;j<=K;++j)
                printf("%d ",c[j]);
            printf("\n");
            // 여기서 return하면 n을 넣지 "않는" 경우 도달 불가
            Combination(c,i,n+1); // i를 선택하지 않는 경우 호출하고
            cnt++;
            return;
        }
        Combination(c,i+1,n+1); // i를 선택하는 경우
        Combination(c,i,n+1); // i를 선택하지 않는 경우
    }
}

int nain () {
    scanf("%d%d",&N,&K);
    int c[N+1], in[N+1];
    for(int i=1;i<=N;++i)
        scanf("%d",&in[i]);
    Combination(in, c, 1, 1);
    printf("cnt: %d",cnt);
}

입력된 N개의 수 중에서. K개를 뽑는 경우를 계산할 수 있다.

 

위 코드와 아래 코드의 차이는 조합의 결과가 저장되는 c[] 배열의 i번째 (i<=K)위치에 저장할 값(N개의 수 중 뽑은 값이) n이냐 아니면 in[n]이냐의 차이이다.

 

전자는 1~N까지의 수 중 K개를 뽑는 경우, i번째로 뽑은 값 n이 (1<= n <=N) c배열에 저장된다.

후자는 유저의 입력 in[N] 배열에 저장된 값 중 K개를 뽑을 때, i번째로 뽑은 값으로 n번째 위치에 있는 값인 in[n]가 c배열에 저장된다.