[BOJ] 16990 마법 장벽 C++

개요

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

16990번: 마법 장벽

 
플레티넘4 난이도의 태그가 없는(?) 문제
지인의 재밌다는 추천에 몇 시간 잡고 풀어냈다.
선수 지식 없고 재밌는 문제,. 강추!!
 

나도 이제 플레티넘 문제 오너,, ^~^

 

풀이

입력을 보면 알겠지만 N <=10,000 M <=200,000으로 생각 없이 풀었다간 무조건 시간 초과가 날 것이 확실했다. 아니지 애초에 장벽이 좌우로 무한이기 때문에 메모리 문제도 있었다.
우선 장벽이 좌우로 무한히 뻗어있기 때문에 이를 해결해야 한다고 생각했다.
패턴의 길이가 1~6이었고(ex: 101, 11, 00110..) 이 수들의 최소 공배수인 60으로 통일해 버리면 벽의 크기를 한정할 수 있다고 생각했다. 이와 동시에 포탄의 발사 위치(P)와 방향(D) (-100,000 <= P, D <= 100,000)을 60으로 나머지 연산을 해버리면 벽의 좌우 문제는 해결된다.
하지만 이렇게 하더라도 시간 문제에는 변함이 없기 때문에 해결책이 필요했다. 뭔가 벽을 합쳐야 될 것 같았고 한참을 고민했는데,,
포탄의 이동 방향(D)을 60으로 나머지 연산한 결과는 0~59가 나오게 된다. 이걸 가지고 벽을 밀면서 합치면 될듯했다. 어차피 포탄은 규칙적으로 이동하기 때문이다. 
포탄의 이동 값만큼 밀면서 합친 장벽에 검사를 하면 끝난다.(초기 포탄 위치도 고려해야함을 주의)
지금 생각해 보면 배열로 합쳐도 됐을 텐데 왜 비트마스킹으로 해서 힘들게 풀었는지 모르겠다.
 

스끼리 늘었다 !~

 
(long long 타입 비트마스킹 시 1LL << n 과 같은 식으로 접미사 LL을 붙여주어야 함을 주의 , , )
 

코드

#include<iostream>
#include<algorithm>
#include<string>
#include<bitset>
using namespace std;
constexpr int LIMIT = 10000;
constexpr long long LENGTH = 60;
long long shell[LIMIT] = {};
long long mergeShell[LENGTH] = {};

long long getShiftedNumber(long long num, int shift)
{
	bool carry = false;
	shift %= LENGTH;
	for (int i = 0; i < shift; i++)
	{
		if (num & 1LL) carry = true;
		num = num >> 1LL;
		if (carry) num |= (1LL<<(LENGTH-1LL));
		carry = false;
	}

	return num;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	int N, M, L;
	int count = 0;
	string pattern;
	int P = 0, D = 0;

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		cin >> L >> pattern;
		for (int k = 0; k < LENGTH; k += pattern.length()) {
			for (int j = 0; j < pattern.length(); j++)
			{
				if (pattern[j] == '1') shell[i] |= (1LL << (j+k));
			}
		}
	}
	for (int i = 0; i < LENGTH; i++)
	{
		mergeShell[i] = shell[0];
		for (int j = 1; j < N; j++)
		{
			mergeShell[i] &= getShiftedNumber(shell[j], (i * (j)));
		}
	}
	for (int i = 0; i < M; i++)
	{
		cin >> P >> D;
		int firstPos = P + D;
		P %= LENGTH;
		D %= LENGTH;
		firstPos %= LENGTH;
		if (firstPos < 0) firstPos = LENGTH + firstPos;
		if (P < 0) P = LENGTH + P;
		if (D < 0) D = LENGTH + D;

		if (mergeShell[D] & (1LL << firstPos)) {
			count++;
		}
	}
	cout << count;
}