취미로 코딩하기

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

이번에 볼 문제는 백준 1648번 문제인 격자판 채우기이다.
문제는 아래 링크를 확인하자.

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

첫 행서부터 마지막 행까지, 같은 행 안에서는 첫 열에서부터 마지막 열까지 순서대로 격자판의 각 칸에 1부터 순서대로 번호를 붙이자.

dp[i][bits]를 i 미만의 칸이 모두 채워져있고, i번 칸을 살펴볼 차례에 bits값에서 켜져있는(1인) 비트에 대응되는 (i 미만의 칸으로 채워지지 않은 첫 행의) 칸이 채워져있는 상태의 경우의 수로 정의하고 식을 세워 dp를 이용하는 것으로 주어진 범위에서의 값들은 계산이 가능하다.

현재 보는 칸이 이미 채워져있다면 해당 칸의 다음 행의 칸은 아직 비어있을 수밖에 없고, 현재 보는 칸이 채워져있지 않다면 그 칸을 윗칸으로 삼는 세로방향 블럭을 배치하거나 (가능하다면) 그 칸을 왼쪽칸으로 삼는 가로블럭 방향을 배치할 수 있다는 점을 이용하여 dp식을 잘 세워보자.

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

#include <iostream>
using namespace std;

int dp[197][16384]; // 각 비트가 0: 비어있음, 1: 차있음

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

	int R, C; cin >> R >> C;
	int mx = 1 << C;
	dp[0][0] = 1;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			int digit = 1 << c;
			int nxtdigit = digit << 1;
			int idx = r * C + c + 1;
			for (int i = 0; i < mx; i++) {
				int dpidxi = dp[idx - 1][i];
				if (i & digit) {
					int& temp = dp[idx][i - digit];
					temp += dpidxi;
					if (temp > 9900) temp -= 9901;
				}
				else {
					int& temp = dp[idx][i + digit];
					temp += dpidxi;
					if (temp > 9900) temp -= 9901;
					if (c + 1 < C) {
						if ((i & nxtdigit) == 0) {
							int& tmp = dp[idx][i + nxtdigit];
							tmp += dpidxi;
							if (tmp > 9900) tmp -= 9901;
						}
					}
				}
			}
		}
	}

	cout << dp[R * C][0];
}