조합 문제 (c++작성)

백준을 풀던 중 조합을 이용하는 문제가 나왔다.

코테에서도 조합문제가 빈번히 등장한다고 하니 조합을 구현하는 연습을 할 필요가 있다.

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

[15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net](https://www.acmicpc.net/problem/15686)

bool next(std::vector<int>& comb, int num) {
    if (comb.empty()) return false;
    int back = comb.back();
    if (back + 1 >= num) {
        comb.pop_back();
        if (next(comb, num - 1)) {
            comb.push_back(comb.back() + 1);
        }
        else {
            return false;
        }
    }
    else {
        comb.pop_back();
        comb.push_back(back + 1);
    }
    return true;
}

위 함수는 내가 백준 15685번을 풀기 위해서 작성한 조합 함수이다.

이 함수는 0부터 num-1까지의 숫자를 n개 고르는 조합 알고리즘이다.

예를 들어 0부터 4까지의 숫자 중 3개를 고르는 조합은

0, 1, 2

0, 1, 3

0, 1, 4

0, 2, 3

0, 2, 4

0, 3, 4

1, 2, 3

1, 2, 4

1, 3, 4

2, 3, 4

\({}_n \mathrm{ C }_k\)

총 10가지다.

매개변수에 0, 1, 2가 들어있는 comb

를 넘기고, 숫자의 총 갯수를 뜻하는 num에 5를 넘기면 다음 조합인 0,1,3을 comb에 넘겨준다. 성공적으로 다음 조합을 계산하면 true를 반환하고 더이상 조합할 수 없으면 false를 반환한다.

더 빠른 알고리즘

배열을 이용하여 훨씬 더 빠르게 만들 수 있다.

https://www.acmicpc.net/problem/1062을 풀기 위해 더 빠른 알고리즘을 구글링하다가 찾은 코드이다. 진짜 간단한데 위 코드를 짤 당시에는 왜 이 생각을 못 했는지 모르겠다.

if (arr[i]) continue; 코드를 통해 꼭 포함되어야하는 원소가 있으면 사전에 이를 설정할 수도 있다.

bool arr[50];
int k = 5;

void dfs(int index, int cnt) {
    if (cnt == k) {
        // print arr
        return;
    }
    for (int i = index; i < 26; i++) {
        if (arr[i]) continue;
        arr[i] = true;
        dfs(i+1, cnt + 1);
        arr[i] = false;
    }
}