백준 12782 비트 우정지수 (파이썬/그리디)

12782번: 비트 우정지수 (acmicpc.net)

12782번: 비트 우정지수

예제 출력은 잘 됐는데 틀렸다고 나와서........

진짜 뭐가 틀렸나 계속 모르겠었는데 아주 복잡한 수를 넣어보니까 결함을 알았다.

<틀린 코드>

T = int(input())
for i in range(T):
    stat = 0
    result = 0
    N, M = input().split()
    for i in range(len(N)):
        if N[i] != M[i]:
            if (stat == 0):
                stat = N[i]
                result += 1
            elif (stat != N[i]):
                stat = 0
            elif (stat == N[i]):
                result += 1
    print(result)

내가 틀렸던 이유: 기존 저 어딘가에 존재했던 0 1 쌍과 맞먹는 1 0 쌍이 나중에 나올수도 있는 건데 그 뒤에 나올 애들에 가려지면서 무조건적으로 + 1 하도록 코드를 짬.

 

결함 발생 원인: 처음에는 제대로 알고 있었으나 나중에 코드가 짜여졌을 때 예제를 충족시킨다는 이유로 이것을 정답이라고 생각함.

 

보완법:답이 안 나올 때는 아주 복잡한 예제를 생각해보거나 처음부터 문제를 다시 읽어보면서 지금 내가 생각하는 알고리즘이 틀렸지 않은가 깨끗한 뇌로 다시 생각해볼 것 

 

<정답 코드>

t = int(input())

for _ in range(t):
    n, m = map(str, input().split())
    one = 0
    zero = 0
    for i in range(len(m)):
        if n[i] != m[i]:
            if m[i] == '1':
                one += 1
            else:
                zero += 1
    print(max(one, zero))

설명: 그리디 알고리즘 답게 아주 탐욕스럽게 1 0 중에 가장 많이 나온것이 곧 정답이다라는 것을 알아낸 방법임

그리디 하면 우선적으로 답의 패턴들을 눈치까서 어떻게하면 정답에 해당하는 숫자가 나올것인지 생각할 것