백준 14391. 종이 조각

tose33 2023. 2. 14. 14:28

14391번: 종이 조각

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고,

www.acmicpc.net

종이의 크기가 최대 4 밖에 안되기 때문에 브루트 포스로 풀수 있다.

이런 류의 최대 크기가 아주 작은 브루트 포스 문제는 가지치기를 그냥 아예 안하는게 쉽게 푸는 방법이다.

종이를 자를수 있는 방법은 다음 경우 밖에 없다.

1. 오른쪽으로 크기 1~4 로 자름

2. 아래로 크기 1~4로 자름

이미 자른 부분은 기록해 나가고,

현재 좌표에서 위의 경우 중 가능한 경우는 모두 수행한다.

그리고 다음 아직 자르지 않은 부분을 찾아서 이동한다.

dfs로 위를 구현하면 알아서 가능한 모든 경우를 탐색한다.