[BOJ] 17136 색종이 붙이기

17136번: 색종이 붙이기

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

6

---

처음에 문제를 보고 생각했던 것은 DP나 DFS, BFS를 생각했었다.

하지만 전혀 풀이방법이 떠오르지 않아서 다른 블로그를 참고해서 해결했다.

 

재귀 함수+BF는 시간 복잡도가 보통 꽤 크기 때문에 보통 배제하고 생각하는데

이 문제는 딱 그런 방법으로 푸는 문제였다.

입력의 크기가 10 X 10 배열로 고정되어 있으므로 충분히 가능할 것 같았다.

실제로 입력의 크기가 그리 크지 않은데도 채점 결과가 16ms나 걸리는 것으로 봐선

꽤나 시간을 잡아먹는 방법인 것 같다.

 

원하는 구간이 1인지 확인하고 0으로 만들었다가 다시 1로 만드는 과정을 보면

시간 복잡도에 집착하는 사람은 비명을 질러버릴지도...?

일단 나조차도 너무 불편해서 다른 방법이 없는지 생각해봤는데 어쩔 수가 없다.

 

 

후기)

삼성 A형 기출문제를 또 풀어봤다.

지금까지 풀었던 문제들 거의 BF 문제였는데 이 문제도 BF 였다.

삼성 A형은 대부분 BF인 것 같다.

 

입력의 크기를 보고 센스껏 코드를 생각해내야 하는데

이런 식의 풀이를 자주 안 해봤다고 그냥 무시해버렸다.

알잘딱깔센하자.

 

for문을 돌릴 때 아주 어이없는 실수를 2개나 했다.

1. 2중 for문에서 break를 한 번만 걸고 왜 안되는지 궁금해했다.

2. for문 초기화를 이번 행에서는 이번 열부터 다음 행부터는 첫 번째 열부터 돌았어야 했는데

이걸 놓쳐서 꽤 시간을 버렸다.