[BOJ] 백준 15361 Izbori

문제 링크

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

15361번: Izbori

 

각 자치주의 후보자 선호도가 주어집니다.

출력 해야하는 정답은

첫 번째로는 주어진 입력 그대로일 때 당선되는 후보를 출력

두 번째로는 후보 K가 당선되기 위해 출마를 취소해야 하는 다른 후보자들의 최소 인원수입니다.

 

일단 브루트포스로 해결하면 될 것 같습니다. 처음 얼핏 생각했을 때는 후보자들이 출마를 취소하는 순서까지 고려해야 한다고 생각했습니다. 근데 순서를 생각하면 $O(N!)$의 시간복잡도로 $M = 15$인 이 문제에서는 불가능합니다.

그러던 중 같이 풀던 다른 분이 브루트포스로 풀었다기에, 순서가 상관이 없다는 걸 깨닫고 해결했습니다.

 

출마하지 않는 후보들의 모든 조합의 수를 고려하면 $O(2^N)$으로 풀 수 있습니다.

 

 

 

정답 코드

#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, k;
int p[200][30];
bool chk[30];    // true이면 후보 i가 출마하지 않는다는 것을 뜻합니다.
 
// foo(): 출마하지 않는 후보들을 모두 고려해서 당선될 후보를 반환합니다.
int foo() {
    int cnt[30] = { 0 };
    for (int i = 0; i < n; i++) {
        int *cur = p[i];
        int j = 0;
        while(chk[cur[j]]) j++;
        cnt[cur[j]]++;
    }
 
    int val = -1, ans = 0;
    for (int i = 1; i <= m; i++) {
        if (val < cnt[i]) {
            val = cnt[i];
            ans = i;
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> p[i][j];
        }
    }
    cout << foo() << '\n';
    int ans = 0x3f3f3f3f;
 
    // t는 원소 m개짜리 집합의 모든 부분집합을 나타냅니다.
    // i번째 비트가 1이면 출마하지 않는 것을 뜻합니다.
    for (int t = 0; t < (1 << m); t++) {
        memset(chk, 0, sizeof(chk));
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if(chk[i+1] = t & (1 << i)) cnt++;
        }
        if (chk[k]) continue;    // 후보 k는 항상 출마해야 하므로 출마하지 않는 집합에 k가 포함되면 고려하지 않습니다
 
        if (foo() == k) {
            ans = ans < cnt ? ans : cnt;
        }
    }
 
    cout << ans;
}