글 읽기 - python) 반례를....도저히...못찾겠습니다...

michasl 2년 전 0

테스트 케이스, 게시판에 있는 반례를 모두 넣어도 정답이 맞게 출력이 됩니다...

얄량한 제 지식으로는 도저히...반례를 못찾겠습니다...

고수님들 많이 조언 부탁드립니다 흑...

n,m = map(int, input().split())
chess = []
change = []
flag = 1
count = 0
result = 9999999

#change안에서 f를 세는 함수
def findMin(x,y,f):
    c = 0
    for i in range(x,x+8):
        c += change[i][y:y+8].count(f)
    return c

for i in range(n):
    change.append(list(0 for i in range(m)))
for i in range(n):
    line = input()
    line = line.replace('W', '0') 
    line = line.replace('B', '1') 
    chess.append(list(map(int, line)))

for i in range(1, n):
    if chess[i][0] == chess[i-1][0]:
        chess[i][0] ^= 1
        change[i][0] = 1
        count += 1
for i in range(n):
    for j in range(1,m):
        if chess[i][j] == chess[i][j-1]:
            chess[i][j] ^= 1
            change[i][j] = 1
            count += 1
#변경횟수가 많을시 change에서 1이 아닌 0으로 바꾸어 세며,
#만약 변경횟수가 동일 할 경우 둘 다 체크하기 위해 -1로 flag 설정
if count == n*m - count:
    flag = -1
elif count > n*m - count:
    flag = 0
if flag != -1:
    for i in range(n-7):
        for j in range(m-7):
            pmin = findMin(i,j,flag)
            if result > pmin:
                result = pmin
elif flag == -1:
    for a in range(2):
        for i in range(n-7):
            for j in range(m-7):
                pmin = findMin(i,j,a)
                if result > pmin:
                    result = pmin
print(result)

djm03178 2년 전 2

전체에서의 변경 횟수가 체크하는 범위를 결정해서는 안 됩니다. 구하고자 하는 답은 아무 곳이나 8x8 격자를 택해서 그 중 최선을 찾는 건데 총 카운트는 그와 별로 상관이 없습니다.

9 17
WBWBWBWBWBWBWBWBB
WBWBWBWBBWBWBWBWB
BWBWBWBWBBWBWBWBW
WBWBWBWBBWBWBWBWB
BWBWBWBWBBWBWBWBW
WBWBWBWBBWBWBWBWB
BWBWBWBWBBWBWBWBW
WBWBWBWBBWBWBWBWB
BWBWBWBWBBWBWBWBB

정답: 0
출력: 1

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

문제

문제

출처

ICPC

python) 반례를....도저히...못찾겠습니다...

michasl 2년 전 0

djm03178 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말