https://www.acmicpc.net/problem/1014
1014번: 컨닝
문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한다. 시험은 N행 * M열 크기의 직사각형 교실에서 이루어진다. 교실은 1*1 크기의 단위 정사각형으로 이루어져 있는데, 각 단위 정사각형은 자리 하나를 의미한다. 최백준은 컨닝을 방지하기 위해서 다음과 같은 전략을 세웠다. 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각
www.acmicpc.net
처음 봤을 땐 어디부터 DP를 적용해나가야 할지 난감했던 문제입니다.
문제를 보면, 한 자리에 누군가를 앉히면 저 화살표로 나타내어진 부분은 다른 사람을 앉힐 수가 없습니다.
위 그림에선 B를 제외하곤 다른 사람을 앉힐 수 없습니다.
점화식을 생각해보기 위해, 문제를 좀 더 생각해보겠습니다.
세로줄 하나만 있을 때를 생각해보면, (M = 1) 이 때는 모든 칸을 사람으로 채워도 됩니다. 같은 세로줄 내부에선 어디 자리에 누굴 앉힌다고 해서, 영향을 받지 않기 때문입니다.
그 옆에 세로줄을 하나 더 추가한다고 생각해본다면, 새로 생긴 세로줄 또한 같은 세로줄 내부에서 누가 앉았다고 영향을 받진 않지만, 전 줄에서 어떻게 앉았느냐에 따라 영향을 받게 됩니다.
만약 전 줄에서 3번째에 사람이 앉았다면, 이번 줄에서는 2, 3, 4번째에서 사람이 앉을 수 없게 됩니다. (앉으면 커닝을 할 수 있는 조건에 만족하게 됩니다.)
따라서 전 줄에서 어떻게 앉았느냐에 따라 이번 줄에서는 앉을 수 있는 경우의 수가 달라지게 됩니다.
이를 이용하여 DP식을 세워보자면
DP(n, m) = (m - 1) 번째 줄에서 n 상태로 사람이 앉았을 때 m 번째 줄에서 나올 수 있는 가장 많은 학생의 수
상태를 표현하기 위해서는 몇 번째 자리에 사람이 앉았는지를 표현할 수 있어야 합니다. 마침 n <= 10 이기 때문에 비트 마스크를 사용하기에도 적절합니다.
이 개념을 가지고 소스코드를 짜 보면 아래처럼 됩니다.
import java.io.*;
import java.util.*;
public class Main {
static int DP[][];
static boolean obstacles[][];
static int N, M;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; ++t) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
DP = new int[1 << N][M];
for(int n = 0 ; n < (1 << N) ; ++n){
Arrays.fill(DP[n], -1);
}
obstacles = new boolean[N][M];
for (int n = 0; n < N; ++n) {
String input = br.readLine();
for (int m = 0; m < M; ++m) {
if (input.substring(m, m + 1).equals("x")) obstacles[n][m] = true; // 장애물 체크
}
}
bw.write(Integer.toString(getDP(0, 0)) + "\n");
}
bw.flush();
bw.close();
}
static int getDP(int n, int m) { // n = 저번 줄에서 사용한 것, m = 현재 줄
if (m == M) return 0; // 모든 줄을 체크한 경우
if (DP[n][m] != -1) return DP[n][m];
int lastN = n; // 현재 턴에서 사용 불가능한 자리 표시 위한 변수
for (int i = 0; i < N; ++i) {
if ((n & (1 << i)) > 0) {
lastN |= (1 << (i + 1)); // 이 자리 또한 사용 불가능
lastN |= (1 << (i - 1)); // 이 자리 또한 사용 불가능
}
}
int result = getDP(0, m + 1); // 아무 학생도 앉히지 않고 다음 줄로 넘어가는 경우 (Default)
for (int i = 1; i < (1 << N); ++i) { // 학생을 앉히는 경우
if ((i & lastN) > 0) continue; // 나올 수 없는 경우의 수 제외하기
int count = 0; // 학생 수를 세기 위함 (비트 연산)
boolean isAvail = true;
for (int j = 0; j < N && isAvail; ++j) {
if ((i & (1 << j)) > 0) { // 이 자리에 학생이 앉아있는 경우
count++;
if (obstacles[j][m]) isAvail = false; // 이 자리가 장애물이 있으면 이 또한 나올 수 없는 경우의 수
}
}
if(!isAvail) continue; // 장애물 체크
result = Math.max(result, getDP(i, m + 1) + count);// 가능한 경우 재귀적으로 전달
}
return DP[n][m] = result;
}
}