백준 1024, 컨닝

문제

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

풀이

처음에는 그냥 dp를 잘 하면 풀 수 있지 않을까해서 조물딱 조물딱 거렸는데 50퍼까지만 가고 맞질 않았다. 나중에 반례 모음집에서 계속 돌려보니까 그냥 못푸는 방식으로 풀었었다. (아마 50퍼까지는 아주 쉬운 케이스만 있는 것 같다. 주의하자)

그래서 다른 풀이를 보고 나름대로 이해해서 다시 작성했다. dp와 비트마스크를 이용했고, 먼저 m의 길이로 나올 수 있는 (ex. 0010101..) 모든 가능한 수를 구한다. 그리고 res에는 해당하는 값에 들어있는 1의 개수를 구한다. 그 뒤에 dp[n-1] 처음이기 때문에 가능한 것을 모두 넣고 그 뒤로부터는 dp[i][possible[j]] = dp[i+1][possible[k]] + res[k], dp[i][possible[j]] 중 최대값을 넣는다. 이때 check 함수를 통해 possible[k] possible[j]이 가능한 배치인지 보고 j와 temp를 비교해서 앉은 자리가 부서진 자리가 아닌지 확인한다. 이걸 모두에 대해서 반복한다.

걸린 시간 : 10시간 이상(3일 투자)

실수

• 이걸 푸는데 온갖 실수와 진을 다뺏기 때문에 따로 작성하지 않는다. 힘들었다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>

using namespace std;

vector<vector<int>> dp(1500, vector<int>(1500, -1));

void dfs(vector<int>& possible, vector<int>& res, int m, int cnt, int prev, int num, int one) {
	if (cnt == m) {
		possible.push_back(num);
		res.push_back(one);
		return;
	}

	else {
		if (prev == 1) {
			dfs(possible, res, m, cnt + 1, 0, num << 1, one);
		}

		else {
			dfs(possible, res, m, cnt + 1, 0, num << 1, one);
			dfs(possible, res, m, cnt + 1, 1, (num << 1) + 1, one + 1);
		}
	}
}

bool check(string temp, int a, int b) { // temp와 a가 호환 가능한지 확인, a와 b가 가능한지 확인
	int temp_num = a;
	for (int i = temp.size() - 1; i >= 0; i--) {
		if (temp[i] == 'x' && (temp_num & 1) == 1) {
			return false;
		}
		temp_num = temp_num >> 1;
	}

	vector<int> temp_a(10, 0);
	vector<int> temp_b(10, 0);
	for (int i = 0; i < temp.size(); i++) { // 원래 비트연산 해야하는데 구현하기 힘들어서 변환
		if ((a & 1) == 1) {
			temp_a[i] = 1;
		}
		if ((b & 1) == 1) {
			temp_b[i] = 1;
		}
		b = b >> 1;
		a = a >> 1;
	}
	for (int i = 0; i < temp.size(); i++) {
		if (temp_b[i] == 1) {
			if (i + 1 < temp.size() && temp_a[i + 1] == 1) {
				return false;
			}
			if (i - 1 >= 0 && temp_a[i - 1] == 1) {
				return false;
			}
		}
	}
	return true;
}

int main() {
	int t;
	scanf("%d", &t);

	for (int h = 0; h < t; h++) {
		vector<int> possible;
		vector<int> res;
		vector<vector<int>> dp(10, vector<int>(1500, 0));
		vector<string> input;
		string temp;
		int n, m;

		scanf("%d %d", &n, &m);
		dfs(possible, res, m, 0, -1, 0, 0);
		for (int i = 0; i < n; i++) {
			cin >> temp;
			input.push_back(temp);
		}

		for (int i = 0; i < possible.size(); i++) {
			if (check(input[n - 1], possible[i], 0)) {
				dp[n - 1][possible[i]] = res[i];
			}
		}

		for (int i = n - 2; i >= 0; i--) {
			for (int j = 0; j < possible.size(); j++) {
				for (int k = 0; k < possible.size(); k++) {
					if (check(input[i], possible[j], possible[k])) {
						dp[i][possible[j]] = max(dp[i][possible[j]], res[j] + dp[i + 1][possible[k]]);
					}
				}
			}
		}

		int r = 0;	
		for (int i = 0; i < possible.size(); i++) {
			r = max(r, dp[0][possible[i]]);
		}
		printf("%d\n", r);
	}

	return 0;
}