난이도

Gold 5

풀이 참고 유무

O

막힌 부분

부분 해로 잘 나누지 못했음

문제

문제 바로가기

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을 출력한다.

예제 입력

3
000
010

예제 출력

3

문제 검토

전구를 전체적으로 바라보는 것은 힘들 것 같다.
주어진 최적의 해를 잘 구할 수 있도록 문제를 부분적으로 나눠보자.

예제 입력에 3크기의 000 010이 힌트가 될 것 같다.

풀이(python)

Python

n=int(input())
cur=list(map(int,input()))
target=list(map(int,input()))

def solve(c,t):
    cnt=0
    for x in range(1,n):
        ##직전이 같다면 컨티뉴
        if c[x-1]==t[x-1]:
            continue
        cnt+=1
        #반전 시키기
        for y in range(x-1,x+2):
            if y<n:            
                c[y]=1-c[y]
    if c==t:
        return cnt
    else:
        return 1e9 
    
res = solve(cur[:], target)
# 첫번째 전구의 스위치를 누르는 경우
cur[0] = 1 - cur[0]
cur[1] = 1 - cur[1]
#비교
res = min(res, solve(cur[:], target) + 1)# min(첫번째 전구x, 첫번째 전구 o)
if res != 1e9:
    print(res)
else:
    print(-1)          

고려해야할 큰 경우의 수 2가지는 첫번째 스위치가 ON인 유무이다.
그 이후 1번째 부터 직전에 인덱스의 전구가 target의 직전에 인덱스의 전구와 다르면 반전 시켜준다.

왜 직전이냐면 전구가 마지막으로 영향을 받아 변경이 되기 위해서는 i-1, i, i+1 중 i-1번째 일 때 변경이 되어야하기 때문이다.
i-1번째를 항상 고려해서 스위치를 on, off 해주는 것이다.
그렇게 되면 그 전구는 이후에는 어떤 경우에도 변경되지 않는다.
그렇게 항상 최적의 해인 타겟에 맞는 전구로 변환을 시켜주게 되고 그렇게 끝까지 갔는데도 실패한다면 -1을 반환하고 아니라면 스위치를 누른 회수를 반환한다.

걸린 시간

x

총평

이 문제는 부분해를 구하는데 부분해가 그 당시 구할 수 있는 최적의 해라는 점에서 그리디 기법이 사용된다.

"문제를 잘게 쪼개서 3개 단위로 그리디 기법을 사용하겠다" 까지는 접근할 수 있었지만, 그 이후 첫번째 스위치를 키고 안 키고의 경우의 수는 물론 i-1번째가 최적의 해를 결정하는 것에 대한 생각은 하지 못했다.

그리디를 풀 때는 문제를 앞에서 것부터 쪼개보고 최대한 단순하게 생각하자.