알고리즘매일매일

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

10X10 인 종이에 있는 1을 색종이를 사용하여 모두 덮는 문제이다.

종이의 크기가 10X10이고 사용할 수 있는 색종이가 최대 5X5개 이므로 완전 탐색이 가능하다

1이 있는 곳에 대해서 5가지의 색종이를 모두 붙여보고 최솟값을 구해주면 된다.

처음에는 그냥 큰 것부터 붙이면 되는 줄 알고 그렇게 구현했다가 틀렸었다.

큰 종이를 먼저 붙여버려서 애매하게 남은 칸이 발생해서 아예 색종이를 덮지 못하는 경우가 생길 수도 있기 때문이다

내가 구현한 방식은 먼저

1. 배열에서 1인 곳(색종이를 덮어줘야 하는 곳)을 찾는다.
   • 없다면 모두 채운 것이므로 현재까지 사용한 색종이의 수를 정답과 비교해주고 return 한다.
   • 있다면 반복문을 break 해주고 1인 곳을 5가지의 색종이로 덮는 모든 경우를 해준다.
2. 이제 각각의 색종이로 덮어보는 모든 경우를 해줄 것인데 k*k크기의 색종이로 덮는다고 했을 때, 처리해줘야 할 조건은 다음과 같다
   • 해당 크기의 색종이가 남아있는지
   • 해당 크기의 색종이로 1인 곳으로부터 k*k칸을 모두 덮을 수 있는지(중간에 0이 없는지)
   • 추가적으로 위의 조건에서 10x10의 범위를 넘어가지 않는지도 잘 체크해주어야 한다.
3. 위의 조건들을 통과해서 k*k크기의 색종이를 사용할 수 있다면 색종이 수를 하나 감소해준다.
4. 그리고 k*k 크기만큼 0으로 만들어준다. 이때 새로운 배열을 만들어서 덮어줘야 한다.
   • 현재 칸(1인 곳)에 대해서 1x1을 사용하는 경우에서부터 5x5를 사용하는 경우는 모두 다른 결과가 나오기 때문에 각각 새로 만들어서 다음 경우로 보내주어야 한다.
   • 즉, 새로 만들어주지 않고 기존의 배열을 사용하면 이미 앞에서 사용한 색종이를 적용한 상태에서 또 덮어버리는 모양이 되기 때문이다.
5. 이제 현재 k*k크기의 색종이로 덮어준 새로운 배열과 함께 사용한 색종이 숫자를 하나 증가시켜서 재귀 호출을 해준다.
6. 재귀 호출에서 돌아온 경우에는 위에서 사용한 색종 이수를 다시 늘려준다. (현재 칸에 대해서 다른 색종이를 사용하는 경우를 해줘야 하기 때문)

(추가) 사용한 색종이 숫자의 최솟값을 찾는 문제이기 때문에 현재 사용한 색종 이수가 정답보다 커질 경우 더 탐색할 필요가 없으므로 43번째 줄에 if(usingnum >= ans) return;를 추가해주면 시간을 더 줄일 수 있다!