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

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

initial

It is the lighting bulb decision-making question. First bulb is affected by 1st and 2nd bulb while second bulb is affected by 1st, 2nd and 3rd bulb. So it is tricky like how do u even think of a pattern? There is an obvious 2^n time complexity solution, where for each index we can either turn on or off the bulb. But it is horrible time complexity so i tried thinking of whether there is a pattern like you see in the image but to no avail.

fatal mistake

before i explain logic, I wasn't properly taking in the string input of “010” and making it a list. a fatal mistake. You have to rstrip the newline character at the end of the input or your list input will come in weirdly. Not do split()

wrong:

lst=list(map(int,input().split())

correct:

target = list(map(int,input().rstrip("\n")))

explain

https://lordofkangs.tistory.com/426

So i googled and this link explained well. The only decision making bit is whether we turn on or off the first bulb. That is it. Lets assume that we turned on the first bulb. That means for the future iterations from 2nd bulb onwards, if the previous bulb is not the target bulb (like if it is turned on instead of being turned off), we need to switch bulb from i-1 to i+1. That way, we know that previous bulb has been switched and is now equal to target bulb. The current iterating bulb might or might not be equal to target bulb but it will be switched by the next iteration. Care not to exceed j while iterating or else we will get index out of range error. (if j<n)

If we dont turn on the first bulb, it is still same logic function but method parameter’s count will be 0 cuz we dont turn on bulb.

oh and also, to make a shallow copy of 1d list, we can either do

list = hola[:] or list=hola.copy()

This logic is very smart and not really decision making but a greedy solution.

solution

n = int(input())
initial = list(map(int,input().rstrip("\n")))
target = list(map(int,input().rstrip("\n")))

def switch(given, count):
    for i in range(1, n):
        if given[i - 1] == target[i - 1]:
            continue

        count += 1
        for j in range(i - 1, i + 2):
            if j<n:
                given[j] = 1 - given[j]

    if given != target:
        return int(1e9)
    else:
        return count

val1 = switch(initial.copy(), 0)

# Turn on the first bulb this time
initial[0] = 1 - initial[0]
initial[1] = 1 - initial[1]
val2 = switch(initial, 1)

print( min(val1, val2) if min(val1, val2) != int(1e9) else -1 )

complexity

n time and space