글 읽기 - 세상 모든 반례를 넣어봤는데 틀렸습니다가 나옵니다 기계가 틀린게 아닐까요?

dongdang 1년 전 3

예제 물론 다 넣어봤구요 질문글에서 반례도 넣어봤습니다.

손수 데이터를 만들어서 넣어도 봤는데 다 찾는건 좀 힘들거 같습니다.

제 인생에 기계는 틀리지 않는다 사람이 문제다 라는 것을 믿어왔는데요

이번 만큼은 기계를 의심하게 되네요...

혹시 잘생기고 섹시한 코더분이 계시다면 제 알고리즘이 무엇이 잘못되었는지 알려주시면 감사하겠습니다...

def chill(start1, end1, start2, end2, key):
    count = 0
    global first, c, minu,s,z
    if first == 'W':   # 첫 문자 값에따라 sec 변수에 다른 값 넣어줌
        sec = 'B'
    else:
        sec = 'W'
    for i in range(start1, end1, key):  # 세로 범위 8
        if i != start1:   # 두 번째 줄부터 첫번째 단어는 색깔을 바꿔서 시작
            temp = first
            first = sec
            sec = temp
        for j in range(start2, end2, key):  # 가로 범위 8
            if first != c[i][j]:  # 색깔이 다르면 색칠 값 + 1
                count += 1
            temp = first   # 비교후 색 비교값을 뒤바꿈
            first = sec
            sec = temp
    if minu > count:  # 제일 적은 색칠 값을 minu 변수에 넣음
        minu = count

a, b = map(int, input().split())
c = []

for i in range(a):
    c.append(input())


minu = a * b # 최소 값 지정
for s in range(a-7):  # 세로 범위 8단위로 끊기
    for z in range(b-7):   #가로 범위 8단위로 끊기
        first = c[s][z]    # 가장 왼쪽 위의 값을 변수에 넣음
        chill(s, 8+s, z, 8+z, 1)   # 왼쪽 위 기준으로 칠해야 할 갯수 구하기
        first = c[7+s][7+z]    # 가장 오른쪽 아래 값을 변수에 넣음
        chill(7+s, s-1, 7+z,z-1,-1)  #오른쪽 아래 기준으로 칠해야 할 갯수 구하기
print(minu)

gyeongmin951 1년 전 1

어떤식으로 흘러가는지 주석으로 달아두시면

더 빠르게 답글이 달릴겁니당. 파이팅

zkoong 1년 전 2

반례입니다.

9 9
BBBBBBBBB
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWBWBWBWW

dongdang 1년 전 1

감사합니다

dongdang 1년 전 2

근데 혹시 반례를 찾으신 방법이 뭔가요?

zkoong 1년 전 2

소스를 읽어 보니 잘못된 부분이 있어서

그걸 반영하여 반례를 만들었습니다.

zkoong 1년 전 2

앗.. 위 반례의 정답은 29 입니다. 이걸 빠뜨렸네요.

dongdang 1년 전 1

답변 감사합니다 수정해서 다시 도전해볼게용

dongdang 1년 전 1

제가 너무 복잡하게 생각해서 첫 글자와 끝 글자로 생각했네용... 첫 글자와 끝 글자가 같은 경우 다른 색상인 경우를 고려를 못해서 틀리는 거군요

덕분에 도움 많이 됐습니다 감사해용

zkoong 1년 전 0

저도 생각하다가 머리가 꼬인적이 많습니다! 저도 덕분에 복습했습니다. 화이팅입니다!

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

문제

문제

출처

ICPC

세상 모든 반례를 넣어봤는데 틀렸습니다가 나옵니다 기계가 틀린게 아닐까요?

dongdang 1년 전 3

gyeongmin951 1년 전 1

zkoong 1년 전 2

dongdang 1년 전 1

dongdang 1년 전 2

zkoong 1년 전 2

zkoong 1년 전 2

dongdang 1년 전 1

dongdang 1년 전 1

zkoong 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말