색종이 붙이기
시간 제한1초메모리 제한512 MB
0과 1로 채워진 10x10 격자에서 1인 칸을 모두 덮도록 1x1부터 5x5까지 각 크기 5장씩 있는 정사각형을 겹치지 않게 붙일 때 필요한 최소 장수를 구한다.
문제
<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류이며, 각 종류의 색종이는 5개씩 있다.
<그림 1>
색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안 되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.
종이가 주어졌을 때, 1이 적힌 모든 칸을 덮는 데 필요한 색종이의 최소 개수를 구해보자.
입력
총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.
출력
모든 1을 덮는 데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.