글 읽기 - [python3] 반례를 못찾겠습니다..(20%오류)

yeop94 4년 전 0

순열을 이용하여 1,2,3,4,5 크기의 색종이들을 덧대는 모든 경우의 수를 생각해 봤습니다.

모든 반례 넣어봤고 확인했는데, 20% 에서 오류가 납니다.

제가 어떤걸 놓치고 있는지 못 찾겠습니다. 도움이 필요합니다..ㅜ

# 색종이
# 10x10 -> 5x5 , 4x4, 3x3, 2x2, 1x1 로 가장 적게 색종이 채우기
from itertools import permutations as pm
import copy

boards=[list(map(int,input().split())) for _ in range(10)]
min_total=26

for case in pm(range(1,5+1)):   # 순열을 이용하여 모든 경우의 색종이 검색
    board=copy.deepcopy(boards)
    cnt=[-1,5,5,5,5,5]
    total=0
    for s in case:   # 현재 순열의 순서대로 색종이 덧대보기
        for i in range(10-s+1):
            for j in range(10-s+1):
                if 0 not in sum([list(board[i+ii][j:j+s]) for ii in range(s)],[]):  # 덧 댄 부분이 모두 1이면
                    if cnt[s]>0:    # 여분의 색종이가 있으면
                        total+=1
                        cnt[s]-=1
                        for ii2 in range(s):    # 색종이를 덧댄다(0 으로 교체)
                            board[i+ii2][j:j+s]=[0]*s

    if 1 not in sum(board,[]):  # 행렬 모든 값에 1이 없으면 최솟값 갱신
        min_total=min(min_total,total)

if min_total<26:
    print(min_total)
else:
    print(-1)

yeop94 4년 전 6

반례

1 1 1 1 1 1 1 0 0 0

1 1 1 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

4 4 4 4 3 3 3 0 0 0
4 4 4 4 3 3 3 0 0 0
4 4 4 4 3 3 3 0 0 0
4 4 4 4 1 2 2 0 0 0
5 5 5 5 5 2 2 0 0 0
5 5 5 5 5 0 0 0 0 0
5 5 5 5 5 0 0 0 0 0
5 5 5 5 5 0 0 0 0 0
5 5 5 5 5 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

답 : 5

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python3] 반례를 못찾겠습니다..(20%오류)

yeop94 4년 전 0

yeop94 4년 전 6

ekfrhkquf12 4년 전 0

jsmin6564 3년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말