[ Baekjoon ] 17136. 색종이 붙이기

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

17136번: 색종이 붙이기

풀이 방법

1인 칸에 대해서 가능한 모든 색종이 종류를 덮어본다. DFS를 이용해서 1인 칸을 모두 덮은 경우, 사용한 최소 색종이 수를 업데이트해나간다.

 

(i, j)를 왼쪽 꼭짓점으로 덮을 수 있는 모든 색종이 종류는 다음과 같이 구한다. 한 변의 길이가 n보다 큰 색종이는 0인 칸 또는 다른 색종이로 덮은 칸까지 덮는다.

for(r=i; r<N; r++){
	if(covered[r][j]) break;
}
for(c=j; c<N; c++){
	if(covered[i][c]) break;
}

n = min(r-i, c-j);
n = min(n, 5); // 1*1, 2*2, ... n*n

 

이렇게 구한 n에 대해서 테스트해본다. 

for(int k=n; k>0; k--){
	if(paper_cnt[k-1] > 0){
		if(!cover(i, j, k)) continue;
		paper_cnt[k-1]--;
		used++;
		num_covered += (k*k);
		test(i, j); // recursive
		num_covered -= (k*k);
		used--;
		paper_cnt[k-1]++;
		uncover(i, j, k);
	}					
}

 

전체 코드는 여기서 확인할 수 있다.