https://www.acmicpc.net/problem/12839
태그 : DP, 비트마스킹, 비트필드DP
사고 과정
상자가 1번부터 N개
내가 풀어야 할 문제는? 카드끼리 모을 떄 최소 횟수가 되도록 하는 것
각 상자마다 해당 상자의 특정 컬러를 선택 시
나가야하는 카드 양 / 들어와야하는 카드 양이 정해진다
1번상자에 각 카드 색을 채워보는 것이 초기 상태
n번 상자에 대해서도 각 카드로 채워보고 해당 색으로 채운 상태를 갱신해보자
각 bitmask 상태마다 해당 비트를 어떤 박스에서 채웠는지 저장해보자이런 사고 흐름을 가지고 풀어나갔다.
그런데 특정 박스에서 특정 카드를 선택하고,
dp 테이블에 그때마다 나가고 들어오는 카드 양을 갱신하자니 계산이 너무 복잡해졌다.
1번 박스에 1번 카드를 넣엇을 때의 최소 이동 수를 넣었다가
-> 2번 박스에 1번 카드를 넣는 경우를 세려면, 기존의 1번박스를 비우고 2번박스로 채워봐야 하는데 이 계산이 너무 복잡해졌다.
이걸 뒤집어 생각해 dp테이블에 저장하니 매우 깔끔해졌다.
그냥 각 상자별로 각 카드를 선택 시 해당 상자에 있는 해당 종류 카드 수를 세면 된다.
그러면 DP테이블이, dp[i][bitmask] = i번 상자까지 고려하여, bitmask 상태의 카드를 선택했을 시,
옮기지 않아도 되는 카드 수의 최대치가 된다.
각 bitmask를 만족하는 최대 카드 수를 저장하게 된다면,
결국 전체 카드 수 - dp[N][(1 << M) - 1]을 해주면 최소 이동 횟수가 될 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/*
상자가 1번부터 N개
내가 풀어야 할 문제는? 카드끼리 모을 떄 최소 횟수가 되도록 하는 것
각 상자마다 해당 상자의 특정 컬러를 선택 시
나가야하는 카드 양 / 들어와야하는 카드 양이 정해진다
1번상자에 각 카드 색을 채워보는 것이 초기 상태
n번 상장에 대해서도 각 카드로 채워보고 해당 색으로 채운 상태를 갱신해보자
각 bitmask 상태마다 해당 비트를 어떤 박스에서 채웠는지 저장해보자
*/
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M, total;
static int [][] box = new int [51][14];
//dp[bitmask][i][j] = i번 상자까지 고려해섯 bitmask 상태로 만들었을때의 최대 제자리 카드 수
static int [][] dp = new int[51][1 << 14];
static void solve() {
for (int i = 0; i <= N; i++) {
for (int j = 0; j < (1 << M); j++) {
dp[i][j] = -1;
}
}
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
for (int bitmask = 0; bitmask < (1 << M); ++bitmask) {
dp[i][bitmask] = dp[i - 1][bitmask];
for (int j = 0; j < M; ++j) {
int prevMask = bitmask - (1 << j);
if (((bitmask >> j) & 1) == 1) {
if (dp[i - 1][prevMask] != -1) {
dp[i][bitmask] = Math.max(dp[i][bitmask], dp[i - 1][prevMask] + box[i][j]);
}
}
}
}
}
sb.append(total - dp[N][(1 << M) - 1]);
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine().trim());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for(int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine().trim());
for(int j = 0; j < M; j++) {
box[i][j] = Integer.parseInt(st.nextToken());
total += box[i][j];
}
}
solve();
System.out.println(sb);
}
}
M의 수를 보고 비트마스킹으로 카드의 경우의 수를 잘 세보자는 아이디어는 생각이 났는데,
카드를 움직여야하는 최소 횟수 대신 고정시킬 수 있는 최대 카드 수를 저장하는 것을 떠올리는 것이 어려웠다.
말하는 감자