[코테] 백준 그리디 2138번 문제

2138번 : 전구와 스위치

문제 링크

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

문제 설명

N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다. 1번 스위치를 눌렀을 경우에는 1, 2번 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N번 전구의 상태가 바뀐다.

N개의 전구들의 현재 상태와 우리가 만들고자 하는 상태가 주어졌을 때, 그 상태를 만들기 위해 스위치를 최소 몇 번 누르면 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

문제 풀이

나도 한참 고민하다가 결국 질문글에서 해답이 있어 코드로 구현해서 통과했다. 자세한 내용은 아래 블로그 참고

https://staticvoidlife.tistory.com/143

# 원하는 문자열을 반전시키는 함수
def reverse(temp) :
    return ['0' if i == '1' else '1' for i in temp]

# 전구 개수 N, 전구들의 현재 상태, 전구들의 바뀌어야 하는 상태 입력
N = int(input())
now = list(input())
change = list(input())

# 본 구문 진행하기 위한 변수들 선언
count_arr = []
count1 = 0
count2 = 0

# temp1은 1번 스위치를 누르고 진행, temp2는 1번 스위치를 누르지 않고 진행
temp1 = now.copy()
temp2 = now.copy()

temp1[0:2] = reverse(temp1[0:2])
count1 += 1
    
# 앞에서부터 반복 
for i in range(1, N) :
    
    # 만약 현상태1,2와 바뀌어야 하는 상태가 같으면 나가기
    if temp1 == change and temp2 == change :
        break

    # i-1이 temp1 현상태와 바뀌어야 하는 상태가 다를때 i-1, i, i+1의 전구를 반전하고 count 1 더하기
    if temp1[i-1] != change[i-1] :
        temp1[i-1:i+2] = reverse(temp1[i-1:i+2]) 
        count1 += 1
        
    # i-1이 temp2 현상태와 바뀌어야 하는 상태가 다를때 i-1, i, i+1의 전구를 반전하고 count 1 더하기
    if temp2[i-1] != change[i-1] :
        temp2[i-1:i+2] = reverse(temp2[i-1:i+2]) 
        count2 += 1

# 반복문이 끝나고 각각의 temp와 바뀌어야하는 전구들의 상태가 동일하면 count 값 배열에 넣기
if temp1 == change : count_arr.append(count1)
if temp2 == change : count_arr.append(count2)
    
# count 배열에 항목이 있으면 그중 작은값 출력, 아니면 -1 출력
if count_arr :
    print(min(count_arr))
else :
    print(-1)