BOJ16201 발코니 공사(C++)

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

태그 : 수학, 구현, 분할정복을 이용한 거듭제곱, 해시맵

사고 흐름

아이디어는 쉬운 편이라는 생각이 들었다.

R, C 값이 매우 컸고 그에 비해 K가 매우 작았다.

그래서 비어있는 대부분의 행의 값들은 메모리에 저장할 것 없이 갯수만 세서 제곱만 잘 해주고,

최대 K개의 값만 map<long long, vector> 로 보관해서 따로 잘 처리 해주면 되겠다고 생각했다.

코드

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

#define MOD 1000000007

long long r, c, k;
map<int, vector<int>> m;
long long ansCase = 1;
long long ansTile;

long long pow(long long base, long long ex) {
	long long ret = 1;
	while (ex) {
		if (ex & 1) {
			ret *= base;
			ret %= MOD;
		}
		base = (base * base) % MOD;

		ex >>= 1;
	}
	return ret;
}

void solve() {
	long long cnt = r;
	while (k--) {
		int a, b;
		cin >> a >> b;
		if (!m[a].size()) {
			--cnt;
		}
		m[a].push_back(b);
	}
	if (c % 2) {
		ansCase = pow(c / 2 + 1, cnt);
	}
	ansTile += cnt * (c / 2);

	for (auto it = m.begin(); it != m.end(); ++it) {
		vector<int>& v = it->second;
		v.push_back(c + 1);
		sort(v.begin(), v.end());

		long long prev = 1;
		long long mul = 1;
		for (int i = 0; i < v.size(); ++i) {
			long long usableTile = v[i] - prev;
			if (usableTile > 1) {
				if (usableTile % 2) {
					mul *= (usableTile / 2 + 1);
				}
				mul %= MOD;
				ansTile += usableTile / 2;
			}
			prev = 1LL + v[i];
		}
		ansCase *= mul;
		ansCase %= MOD;
	}
}

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

	cin >> r >> c >> k;
	solve();
	cout << ansTile << ' ' << ansCase;
}

후기

pow 구현부에서 나머지 처리 안해서 WA를 받았다. 사소한 디테일을 놓치지 말 것