[백준] 17136 색종이 붙이기

---

10 * 10 격자판의 1을 모두 덮는 최소 색종이 개수를 구하는 문제이다.

 

단순 반복문 보다는 백트래킹 알고리즘을 사용하면 쉽게 해결할 수 있다.

 

1. 색종이 사이즈 배열 S에 지금까지 사용한 색종이의 개수를 저장한다.

2. 재귀 함수를 사용한다. 열 번호를 하나씩 증가시키고 열 번호가 10일 경우 행 번호를 하나 증가시키고 다시 열번호를 0으로 초기화한다.

3. 열번호가 10일 경우 색종이의 총 개수를 반환하며, 가장 작은 경우를 출력한다.

 

색종이 사이즈가 s * s라고 할때 s에 0 - 4를 대입하여 반복한다. 만일 해당 색종이를 5장 미만 사용했다면 해당 구간의 배열을 완전탐색하여 모든 값이 1인 경우 색종이로 덮는다. 이는 1을 0으로 치환하는 것으로 대신한다. 덮은 후 열 번호를 s+1 증가시키고 재귀 호출한다.

 

Python