[BOJ 14473 // C++] ぬいぐるみの整理 (Plush Toys)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14473번 문제인 ぬいぐるみの整理 (Plush Toys)이다.
문제는 아래 링크를 확인하자.

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

14473번: ぬいぐるみの整理 (Plush Toys)

 

인형의 종류 M의 입력 제한이 20이하인 점을 눈여겨보자.

 

M개의 원소로 구성된 인형의 집합 A의 공집합이 아닌 부분집합 S를 생각하자. S에 속한 인형들을 맨 왼쪽서부터 채워넣을 때 기존과 다른 위치에 있게 되는 인형의 수를 f(S)라 할 때, f(S)는 S에서 하나의 원소 p를 제거한 각 집합 X에 대하여 min(f(X) + (X를 채운 뒤 p들을 채워넣을 때 기존 위치에 적힌 수가 p가 아닌 칸의 개수))으로 계산해나갈 수 있다.

 

집합 A의 각 부분집합은 각 원소가 들어있으면 1, 없으면 0과 같이 표현해 이진수로 표현할 수 있으므로, bit DP를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int iterend = 1;
int arr[100001];
int psum[21][100001];
int dp[1048576];
int prog[1048576];
int cnt[21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	iterend <<= M;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		cnt[arr[i]]++;
		for (int k = 1; k <= M; k++) psum[k][i] = psum[k][i - 1];
		psum[arr[i]][i]++;
	}

	for (int i = 1; i < iterend; i++) dp[i] = 1000000007;
	dp[0] = 0;

	for (int i = 0; i < iterend; i++) {
		int tmp = 1;
		if (!(i & tmp)) {
			dp[(i | tmp)] = min(dp[(i | tmp)], dp[i] + cnt[1] - (psum[1][prog[i] + cnt[1]] - psum[1][prog[i]]));
			prog[(i | tmp)] = prog[i] + cnt[1];
		}
		for (int k = 2; k <= M; k++) {
			tmp <<= 1;
			if (!(i & tmp)) {
				dp[(i | tmp)] = min(dp[(i | tmp)], dp[i] + cnt[k] - (psum[k][prog[i] + cnt[k]] - psum[k][prog[i]]));
				prog[(i | tmp)] = prog[i] + cnt[k];
			}
		}
	}

	cout << dp[iterend - 1];
}