BOJ 1176 - 섞기 (bit, dp)

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

dp using bitfield중 기본문제.

 

<문제설명>

최대 16명의 학생들의 키와 k값이 주어진다. 학생들을 일렬로 배치했을 때 모든 학생들의 인접한 학생과의 키 차이가 k이초과인 경우의 수를 구해라.

 

<풀이 - 재귀>

f(s,t) : 현재 s, 마지막으로 배치된 인원이 t인 경우의 수

ans = f(0,n)   -- (t==n인 경우 아무 인원이나 배치할 수 있다. [0base])

 

s==(1<<n)-1인 경우 1(성공)을  반환하도록 기저를 처리한다.

 

s에 포함되지 않은 i에 대해서, 마지막으로 배치된 인원과의 키 차이가 k 초과인 경우만 세준다

 

<코드 - 재귀>

ll dp[(1 << 16) + 2][17];
int n, k, a[17];
ll f(int s, int t) {
	if (s == (1 << n) - 1)
		return 1;

	ll& ret = dp[s][t];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < n; i++) 
		if ((s & (1 << i)) == 0 && (abs(a[i] - a[t]) > k || t==n))
			ret += f(s | (1 << i), i);
	
	return ret;
}

int main() {
	FAST;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	memset(dp, -1, sizeof(dp));
	cout << f(0, n) << '\n';
}

 

<풀이 - for문>

f(i,j) : 인원 i, 마지막 배치 j인 경우의 수

ans = sum( f((1<<n)-1, i ) )  ( 0<= i <n )

 

인원 i에 포함되지 않은 p에 대해 p를 배치할 수 있다면

d[i | (1<<p) ][p] += d[i][j]

 

d[(1<<i)][i] = 1로 초기화 해두고 시작.

 

<코드 - for문>

const int MAX = (1<<16)+1;
int main() {
	FAST;
	int n, k, a[17]; cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	ll d[MAX][17]{ 0 };
	for (int i = 0; i < n; i++) d[1 << i][i] = 1;

	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
			for (int l = 0; l < n; l++)
				if (!(i >> l & 1) && abs(a[j] - a[l]) > k)
					d[i | (1 << l)][l] += d[i][j];

	ll ans = 0;
	for (int i = 0; i < n; i++) ans += d[(1 << n) - 1][i];
	cout << ans << '\n';
}