백준 15361번 Izbori

#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
 
int n, m, k;
 
int arr[100][15];
int visited[100][15];
 
int cnt[16];
//no[] 0이면 후보 1이면 사퇴
bool no[16];
 
void win() {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (no[arr[i][j]] == 1) continue;
            cnt[arr[i][j]]++;
            break;
        }
    }
}
int DFS(int pos,int num) {
    //뽑아야하는 후보의 경우 다음케이스넘어감.
    if (pos == k) DFS(pos + 1, num);
    
    //모든 후보들의 사퇴여부를 결정했을때
    if (pos == m + 1) {
        win();
        int Maxcnt = 0;
        int eq=0;
        for (int i = 1; i <= m; i++) {
            if (Maxcnt < cnt[i]) {
                Maxcnt = cnt[i];
                eq = i;
            }
        }
        if (eq == k ) {
            return num;
        }
        else
            return 987654321;
    }
    int ret = 98764321;
    for (int i = 0; i < 2; i++) {
        no[pos] = i;
        if (i == 0) { //pos번 후보가 사퇴하지않는 경우
            ret=min(ret,DFS(pos + 1, num));
        }
        else
        {            //pos번 후보가 사퇴하는 경우
            ret = min(ret, DFS(pos + 1, num + 1));
        }
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int no[16];
    cin >> n >> m >> k;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    memset(no, 0, sizeof(no));
    memset(cnt, 0, sizeof(cnt));
 
    for (int i = 0; i < n; i++) {
        cnt[arr[i][0]]++;
    }
    int Max = 0;
    int pos = 0;
    for (int i = 1; i <= m; i++) {
        if (Max < cnt[i]) {
            Max = cnt[i];
            pos = i;
 
        }
    }
    cout << pos << endl;
    cout << DFS(1, 0);
 
    return 0;
}
 

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

후보가 모두 표를 동일하게 받은 경우에 대한 경우를 고려하지않아서 계속 틀렸습니다. 

사퇴여부를 모두 고려한다음 계산을 빠르게 해주는게 문제의 핵심 포인트입니다.