그리디 - 2138번: 전구와 스위치

경우의 수:
1) 첫번째 스위치 누르지 않는 경우
2) 첫번째 스위치 누르는 경우
위 두 경우만 확인하면 그 이후 스위치는 직전 스위치 상태에 따라 자동으로 결정됨 (다르면 누르기)

• 첫번째 스위치 누르지 않는 경우부터 확인해야 최소 횟수 먼저 찾을 수 있음

n = int(input())

state = list(map(int, list(input())))
dest = list(map(int, list(input())))

def switch(i, lights):
    for idx in range(i - 1, i + 2):
        if idx < 0 or idx > n - 1:
            continue
        lights[idx] ^= 1 # XOR연산자로 0 -> 1, 1 -> 0 으로 변환!

# 0) 입력받은 state와 dest가 동일한 경우
if state == dest:
    print('0')

else: 
    # 1) 맨 앞 전구 누르지 않는 경우
    cnt = 0
    state_1 = state[:] # 리스트 복사해서 사용

    for i in range(n):
        if i == 0: # 맨 앞 전구는 무조건 누르지 않기
            continue
        elif state_1[i - 1] != dest[i - 1]: # 그 외 전구는 i - 1이 다를 때만 i 눌러서 맞추기
            switch(i, state_1)
            cnt += 1

    if state_1 == dest: # 경우 1에서 찾았다면
        print(cnt)

    else: # 답을 찾지 못했다면

        # 2) 맨 앞 전구 누르는 경우
        cnt = 0
        state_2 = state[:] # 리스트 복사해서 사용

        for i in range(n):
            if i == 0: # 맨 앞 전구는 무조건 누르기
                switch(i, state_2)
                cnt += 1
            elif state_2[i - 1] != dest[i - 1]: # 그 외 전구는 i - 1이 다를 때만 i 눌러서 맞추기
                switch(i, state_2)
                cnt += 1

        if state_2 == dest:
            print(cnt)
        else:
            print('-1')