DP, 비트마스킹
문제를 보고 생각한 부분
DP 구성
DP 진행
- 두가지의 경우로 나누어졌다.
- 구입이 가능한 상황에, 다음 진행의 DP값이 한번도 변경이 안되어 있는 상황 (= 초기값이 저장되어있을 때)
- 구입이 가능한 상황에, 다음 진행의 DP값이 초기값이 아니고, 앞서 저장했던 값보다 더 작은 값으로 갱신 가능한 상황.
#include <iostream>
#include <string>
#include <string.h>
using namespace std;
string a123;
int n;
int data_[16][16];
int dp[(1 << 16)][16];
int dp2[(1 << 16)][16];
void dp_(int start,int dpcnt)
{
//dp[dpcnt][start] -> dp[a][i]로 연결
for (int i = 0; i < n; i++)
{
//자기자신, 중복 구입 방지
if (i == start || (dpcnt & (1<<i)) != 0)
continue;
//a는 i번째의 예술가가 구입한 상황의 구입자들 상태
int a = dpcnt | (1 << i);
//비어있지 않은데, 더 좋은 경우 발생시 들어가
if (dp[a][i] > data_[start][i] && dp[a][i]!=-1 && data_[start][i] >= dp[dpcnt][start])
{
dp[a][i] = data_[start][i];
dp_(i, a);
}
//처음에 비어있고, 조건을 충족할때 들어가
else if (dp[a][i] == -1 && data_[start][i] >= dp[dpcnt][start])
{
dp[a][i] = data_[start][i];
dp2[a][i] = dp2[dpcnt][start] + 1;
dp_(i, a);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++)
{
cin >> a123;
for (int j = 0; j < n; j++)
{
data_[i][j] = a123[j] - '0';
}
}
dp_(0,1);
dp[1][0] = 0;
int max = -99;
//구입한 인원 최대값 구하기
for (int i = 0; i < (1 << n); i++)
{
for (int j = 0; j < 15; j++)
{
if (max < dp2[i][j])
{
max = dp2[i][j];
}
}
}
//맨 처음 구입자 1번 고려
cout << max + 1;
return 0;
}