Problem Solving/DP
BOJ 11578 - 팀원 모집
Vjerksen
2017. 9. 30. 15:45
문제 링크
https://www.acmicpc.net/problem/11578
문제 해결
1. N(사람의 수)와 M(문제의 수)가 최대 10이므로 비트마스크 DP를 사용해서 문제 해결.
2. dp[a][b] = a만큼의 사람이 b만큼 문제를 풀었을 때의 최소 사람.
주의할 점 || 생각해볼 점
-
참고
-
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
explanation in vjerksen.tistory.com | |
*/ | |
#include<iostream> | |
#include<cstdio> | |
#include<string> | |
#include<cstring> | |
#include<algorithm> | |
#include<queue> | |
#include<set> | |
#include<ctime> | |
#include<vector> | |
using namespace std; | |
int N,M; | |
vector<int> a[15]; | |
int dp[1<<11][1<<11]; | |
int go(int n,int p){ | |
if(n==N){ | |
if(p==(1<<M)-1){ | |
return 0; | |
} | |
else{ | |
return 1e8; | |
} | |
} | |
int& ret = dp[n][p]; | |
if(ret!=-1) return ret; | |
ret=1e8; | |
ret = min(ret,go(n+1,p)); | |
for(int i=0;i<a[n].size();i++){ | |
int next = a[n][i]; | |
if(!(p&(1<<next))) | |
p+=(1<<next); | |
} | |
ret = min(ret,go(n+1,p)+1); | |
return ret; | |
} | |
int main(){ | |
memset(dp,-1,sizeof(dp)); | |
cin >> M >> N; | |
for(int i=0;i<N;i++){ | |
int u; | |
scanf("%d",&u); | |
for(int j=0;j<u;j++){ | |
int temp; | |
scanf("%d",&temp); | |
a[i].push_back(temp-1); | |
} | |
} | |
int ans = go(0,0); | |
if(ans>=1e8) | |
printf("-1"); | |
else | |
printf("%d",ans); | |
return 0; | |
} |
※ 정확하고 부드러운 태클은 언제나 환영입니다.