[Python/BOJ] 백준2138 전구와 스위치_그리디

 

 

 

이해하는게 참 어려웠던 문제다. 

앞서 풀었던 행렬처럼 (https://what-am-i.tistory.com/408)

그리디이기 때문에 한번만 돌면서 다르면 바꾸고 이런 식일거라고 생각했다.

 

 

 

 

 

그런데 이 문제는 i-1, i, i+1 이 변경이되고 가장 앞과 가장 뒤는 2개씩만 변경되니까 어떻게 나눠야할지 막막했다. 

 

 

찾은 방법은 바로! 

내 앞에 있는 전구와  동일한 위치의 목표로 하는 전구가 다르면 나를 변경시킨다! 

 

앞에 있는 전구를 보기 때문에 첫번째 있는 전구는 볼 전구가 없다. 

그래서 첫번재 전구를 키는 경우, 안키는 경우 두가지를 확인하여 최소값을 찾으면 된다. 

 

 

 

 

# 0은 1으로 , 1은 0으로 
def change(num) :
    return 1 - num


def flip(state,cnt) :
	# 첫번째 전구를 킨다. 
    if cnt == 1 :
        state[0] = change(state[0])
        state[1] = change(state[1])
    for j in range(1,n) :
        if state[j-1] != goal[j-1] :
            cnt+=1 
            state[j-1] = change(state[j-1])
            state[j] = change(state[j])
            # 마지막 원소가 아니라면 
            # 3개를 변경 
            if j != n-1 : 
                state[j+1] = change(state[j+1])
    if state == goal : return cnt 
    else : return -1 
        
if __name__=="__main__" :
    n = int(input())
    origin = list(map(int,list(input())))
    goal = list(map(int,list(input())))

	# 첫번째 전구를 안바꾼다. 
    ans1 = flip(origin[:],0)
    # 첫번째 전구를 바꾼다.
    ans2 = flip(origin[:],1)
    
    # 바꿀수있는 방법이 없는경우
    if ans1 == -1 and ans2 == -1 : print(-1)
    # -1일경우에는 그 값이 min이 되어버려서 둘 다 양수라면 min을 , 
    # 아니라면 max를 출력 
    else :
        print(min(ans1,ans2)if (ans1>=0 and ans2>=0) else max(ans1,ans2))

 

 

 

 

 

 

 

아니 2주만에 푸는데 완전히 까먹었네...😂

🐾20221014

 

 

 

 

 

 

 

 

참고 블로그 : 

https://fre2-dom.tistory.com/55

[baekjoon] 백준 2138번(파이썬): 스위치