[python] 백준 17136 색종이 붙이기

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

17136번: 색종이 붙이기

 

문제 해결

• 여러가지 경우의 수를 계산해야한다.
• 재귀함수를 통해 모든 경우의 수를 계산해서 최소의 값을 구할 수 있다.
• 각 크기의 색종이가 5개이므로 5개를 넘어가면 더이상 그 색종이를 사용하지 않는다.

 

CODE

import sys
input = sys.stdin.readline
INF= sys.maxsize

def solve(x, y, cnt):
    global ans
    if y >= 10:
        ans = min(ans, cnt)
        return
    
    if x >= 10:
        solve(0, y+1, cnt)
        return
    
    if paper[x][y] == 1:
        for k in range(5):
            if used_paper[k] == 5: 
                continue
            if x + k >=10 or y + k >= 10: 
                continue

            flag = 0
            for i in range(x, x+k+1):
                for j in range(y, y+k+1):
                    if paper[i][j] ==0:
                        flag = 1
                        break
                if flag: 
                    break
            if not flag:
                for i in range(x, x+k+1):
                    for j in range(y, y+k+1):
                        paper[i][j] =0
                used_paper[k] += 1
                solve(x+k+1, y, cnt+1)
                used_paper[k] -= 1

                for i in range(x, x+k+1):
                    for j in range(y, y+k+1):
                        paper[i][j] = 1
    else:
        solve(x+1,y,cnt)
if __name__=='__main__':
    paper = [list(map(int, input().split())) for _ in range(10)]
    used_paper = [0 for _ in range(5)]
    ans = INF
    solve(0, 0, 0)
    print(ans) if ans != INF else print(-1)