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

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

2138번: 전구와 스위치

 

 

---

 

1. Preview

시간 복잡도: O(N)

 

공간 복잡도: O(N)

 

참고 : https://velog.io/@waoderboy/BOJ-%EB%B0%B1%EC%A4%80-2138-%EC%A0%84%EA%B5%AC%EC%99%80-%EC%8A%A4%EC%9C%84%EC%B9%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC 

 

유형: 그리디

 

 

---

 

2. 초기 접근 방법

중앙점이 틀리면 스위치를 눌러 바꾸는 형식으로 접근하였다.. (틀림)

 

 

---

 

3. 생각

문제는 푸는데 핵심인 Key는 2가지가 있다.

 

1) 전구[i-1] 상태 값에 따라 스위치[i] OX 가 결정된다.

이는 순차적으로 탐색한다면, i번째 스위치가 i-1번째 전구의 상태를 결정할 마지막 스위치이기 때문이다.

 

2) 스위치[0] OX 체크

스위치 탐색은 0번 전구의 상태 값을 확인해야 하므로, 기본적으로 1번 스위치부터 탐색을 한다.

하지만 이 경우에 0번째 스위치를 누르냐, 안 누르냐에 따라서 초기 전구의 상태가 완전히 달라진다.

따라서 0번째 스위치를 누르는 경우와, 누르지 않는 경우를 고려해 2번 비교를 해야 한다.

 

 

---

 

4. 코드

def change(A, B):
    Acopy = A[:]
    cnt = 0
    for i in range(1, N):
        # i-1 전구 상태 값에 따라 스위치 OX가 결정된다.
        if Acopy[i-1] == B[i-1]:
            continue

        cnt += 1
        for j in range(i-1, i+2):
            if j < N:
                Acopy[j] = 1 - Acopy[j] # Good

    if Acopy == B: # 목표하는 전구 상태가 됐을 시
        return cnt
    else:
        return -1



N = int(input())
S = list(map(int, input()))
E = list(map(int, input()))

# 0번째 스위치 X
res = change(S, E)
if res != -1:
    print(res)

# 0번째 스위치 O
else:
    S[0] = 1 - S[0]
    S[1] = 1 - S[1]

    res = change(S, E)
    if res != -1:
        print(res+1)
    else:
        print(-1)