백준 16201번: 발코니 공사

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

16201번: 발코니 공사

---

도미노의 모양새에 대한 조건이 너무 강력해서 티어가 낮아진 문제입니다.

 

이 문제는 colorless한 $1 \times 2$ 도미노의 타일링을 다루고 있고 특별한 조건으로 "가로로만 놓을 수 있음"이 있습니다. 또 하나의 조건은 도미노를 최대한 많이 써야만 한다는 것입니다. 그래서 각 row에 대해 총 몇 개의 도미노를 놓을 수 있는지만 생각하면, 그 다음부터는 단순 계산의 영역이 됩니다.

---

$K$가 $R$에 비해 일반적으로 매우 작은 값이므로, $R-K$개 totally broken row를 먼저 설명해보겠습니다.

 

$C$가 만약 짝수라면, 도미노를 사용하여 이러한 row를 가득 채울 수 있습니다. 따라서 row 1개당 경우의 수는 1입니다.

그때 타일의 수는 $+\frac{C}{2}$입니다.

 

$C$가 만약 홀수라면, 도미노를 최대한 사용했을 때 한 칸이 남습니다. 따라서 row 1개당 경우의 수가 $\lfloor \frac{C}{2} \rfloor + 1$입니다.

그때 타일의 수는 $+\lfloor \frac{C}{2} \rfloor$입니다.

---

이제 $K$개 row를 생각해보겠습니다. 이들의 특징은 부서지지 않은 칸의 위치에 따라 경우의 수가 달라질 수 있다는 것입니다. 그러므로 특정 row의 부서지지 않은 칸끼리만 모아서 생각해볼 필요가 있습니다. 저는 여기서 $R_{i}$와 $C_{i}$를 오름차순으로 정렬하고 풀이를 시작했습니다. $( 1 \leq i \leq K)$

 

이렇게 오름차순으로 정렬한 후에는, 각 칸 사이에 부서진 칸의 개수가 몇 개인지를 세서, totally broken row에 관한 논의를 다시 반복하면 됩니다. 주의할 점은 부서지지 않은 칸 사이만이 아니라, 첫 칸과 처음으로 부서지지 않은 칸, 마지막으로 부서지지 않은 칸과 마지막 칸 사이의 칸들도 고려해야 합니다. 끝으로 문제에서 지시한 대로 타일의 수를 modulo 취하지 않으면 정답을 받을 수 있습니다. 다음은 제 코드입니다.

#include <stdio.h>
#include <stdlib.h>
#define mod 1000000007

typedef struct {
	long long R;
	long long C;
} position;
position array[1000];

int compare (const void* m, const void* n);

int upper_bound_R (int S, int E, long long K);
int lower_bound_R (int S, int E, long long K);

long long power_modular (long long x, long long y);

int main(void) {
	
	long long R, C, K;
	scanf("%lld %lld %lld", &R, &C, &K);
	
	for (int i = 0; i < K; i++) {
		scanf("%lld %lld", &array[i].R, &array[i].C);
	}
	qsort(array, K, sizeof(position), compare);
	
	long long count_totally_broken_row = R, count_tile = 0, way_tiling = 1;
	for (int i = 0; i < K; i++) {
		int upper = upper_bound_R (0, K-1, array[i].R);
		int lower = lower_bound_R (0, K-1, array[i].R);
		if (array[lower].R == array[upper].R) {
			upper++;
		}
		
		for (int j = lower; j < upper; j++) {
			int length = (j == lower) ? array[lower].C - 1 : array[j].C - array[j-1].C - 1;
			way_tiling = (length % 2) ? (way_tiling * ((length / 2) + 1) % mod) : way_tiling;
			count_tile += length / 2;
		}
		
		int last_length = C - array[upper - 1].C;
		way_tiling = (last_length % 2) ? (way_tiling * ((last_length / 2) + 1) % mod) : way_tiling;
		count_tile += last_length / 2;
		
		i = upper - 1;
		count_totally_broken_row -= 1;
	}
	
	int way_tiling_totally_broken = (C % 2) ? C/2 + 1 : 1;
	count_tile += count_totally_broken_row * (C/2);
	way_tiling = way_tiling * power_modular(way_tiling_totally_broken, count_totally_broken_row) % mod;

	printf("%lld %lld", count_tile, way_tiling);
	return 0;
}

int compare (const void* m, const void* n) {
	position a = *(position*)m;
	position b = *(position*)n;
	if (a.R == b.R) {
		return a.C - b.C;
	}
	else {
		return a.R - b.R;
	}
}

int upper_bound_R (int S, int E, long long K) {
	while(S < E) {
		int M = (S + E) / 2;
		if(array[M].R <= K) {
			S = M + 1;
		}
		else {
			E = M;
		}
	}
	return E;
}

int lower_bound_R(int S, int E, long long K) {
    while(S < E) {
		int M = (S + E) / 2;
		if(array[M].R < K) {
			S = M + 1;
		}
		else {
			E = M;
		}
    }
    return E;
}

long long power_modular (long long x, long long y) {
	long long result = 1;
	while (y) {
		if (y % 2) {
			result = result * x % mod;
		}
		x = x * x % mod;
		y /= 2;
	}
	return result;
}

(C11, 0ms, 1116KB, 제출번호 54623913)

---

오랜만에 qsort, lower_bound, upper_bound를 써보니 생각보다 구현이 오래 걸렸습니다...

 

이 문제가 골드에 머물게 된 가장 큰 원인은 가로로만 놓을 수 있음 같은데, 제한이 풀리면 어떻게 될까요? Graph Theory에서 해당 문제를 다뤘던 걸로 기억합니다. 아마 백준에서 비슷한 상황을 본 적 있었는데...