[백준] 2138번: 전구와 스위치 Python

https://www.acmicpc.net/problem/2138

2138번: 전구와 스위치

 

시도 1 : 메모리초과 (PyPy), 시간초과 (Python)

import sys
sys.setrecursionlimit(10**7)
flag = False
answer = 0

N = int(input())
a = list(map(int, list(input())))
b = list(map(int, list(input())))
'''
0 : ON 
1 : OFF
직전에 누른 스위치는 누르지 않는다 ! 
'''
def check(arr1, arr2):
    if arr1 == arr2:
        return True
    return False

# 이미 a == b 인 경우
if check(a, b):
    print(0)
    exit(0)

def dfs(switch, arr, cnt):
    if cnt == 10000:
        return -1
    # switch 넣었을 때 검토
    if switch == 0:
        arr[0] = (not arr[1])
        arr[1] = (not arr[0])
    elif switch == N-1:
        arr[N-1] = (not arr[N-1])
        arr[N-2] = (not arr[N-2])
    else:
        arr[switch-1] = (not arr[switch-1])
        arr[switch] = (not arr[switch])
        arr[switch+1] = (not arr[switch+1])

    if check(arr, b):
        return cnt

    for next in range(N):
        if next == switch:
            continue
        dfs(next, arr, cnt+1)

for i in range(N):
    result = dfs(i, a, 1)
    if result != -1:
        flag = True
        answer = min(answer, result)

if flag:
    print(answer)
else:
    print(-1)

 

시도2: Greedy 

문제에서 조건으로 index 0 번째 switch 를 누르면 index 0, 1 만 반전된다고 주어졌다. 따라서 경우를 2가지로 나누어 확인한다. 

• index 0 부터 확인해 나가는 경우와 index 1 부터 확인해 나가는 경우가 있다.
• 이 두가지 경우 중에서, switch 누르는 개수 (= count 값) 가 작은 것이 답이 된다. 

또한 index N-1번째 switch를 누르면, N-2, N-1 번의 전구들만 값이 반전 된다. 따라서 index 처리를 해주어야 한다. 

N = int(input())
a = list(map(int, list(input())))
b = list(map(int, list(input())))

temp1 = a[:]
temp2 = a[:] # deep copy

def check(arr1, arr2):
    if arr1 == arr2:
        return True
    return False

# from index 0
def from_zero(arr):
    count = 1
    arr[0] = (not arr[0])
    arr[1] = (not arr[1])

    for i in range(1, N):
        if arr[i-1] != b[i-1]: # i-1, i, i+1 모두 동일해야 하므로 i-1 부터 체크
            count += 1
            arr[i-1] = (not arr[i-1])
            arr[i] = (not arr[i])
            if i != N-1:
                arr[i+1] = (not arr[i+1])

    if check(arr, b):
        return count
    return -1
# from index 1
def from_one(arr):
    count = 0
    for i in range(1, N):
        if arr[i-1] != b[i-1]:
            count += 1
            arr[i - 1] = (not arr[i - 1])
            arr[i] = (not arr[i])
            if i != N-1:
                arr[i+1] = (not arr[i+1])
    if check(arr, b):
        return count
    return -1

result1 = from_zero(temp1)
result2 = from_one(temp2)

if result1 != -1 and result2 == -1:
    print(result1)
elif result1 == -1 and result2 != -1:
    print(result2)
elif result1 == -1 and result2 == -1:
    print(-1)
else:
    print(min(result1, result2))