경우를 나눠서 생각하면 최적해로 도달하는 경이로운 그리디 알고리즘(전구와 스위치, 전구 상태 바꾸기)

1. 문제

 

2138번: 전구와 스위치 (acmicpc.net)

2138번: 전구와 스위치

 

2. 풀이

 

핵심 해법은 0번 전구를 누를 수 없다고 할 때, 1번부터 n-1번까지 눌러봐서 원하는 상태에 도달할 수 있는지 체크하고

 

다음은 0번 전구를 반드시 누를때, 1번부터 n-1번까지 눌러봐서 원하는 상태에 도달할 수 있는지 체크해본다.

 

둘다 불가능하면 바꿀수 없는 것일테고, 하나라도 가능하다면 최소로 누른 횟수가 정답이 될 것이다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------

 

처음에 0번을 누를 수 없다고 가정하면,

 

1번부터 누르는데 1번은 언제 눌러야할까?

 

0번 상태는 오직 1번을 누르지 않는 이상 절대로 바꿀 수 없으므로,

 

현재 0번 상태가 목표로 하는 0번 상태와 다르다면 1번을 눌러야 할것이고, 그렇지 않다면 1번을 누르면 안될것이다

 

예를 들어 현재 000이고 원하는 상태가 010이면... 0번은 누를 수 없을때, 1번을 눌러야하는가?

 

하지만 1번을 누르면 111이 되고, 앞으로는 0번을 바꿀 수 없다. 그러나 0번은 0으로 되어야하므로 1번을 누르면 안된다.

 

다음 2번으로 넘어가서 2번을 눌러야하는가? 말아야하는가?

 

1번이 1로 바뀌어야하므로 2번을 무조건 눌러야한다. 그러면 011인데, 원하는 상태는 010이므로 0번을 누르지 않은 경우에는 불가능 한것이다.

 

-----------------------------------------------------------------------------------------------------------------------------------------------------

 

다음으로, 처음에 0번을 눌렀다고 가정하면.. 110인데.. 이제 1번을 눌러야하는가?

 

당연히 0번은 목표가 0으로 바꿔야하므로, 1번을 눌러줘야한다. 001

 

다음 2번을 눌러야하는가? 1번은 목표가 1로 바꿔야하므로 눌러줘야한다. 010

 

0번을 눌렀다고 가정하면, 3번만에 010으로 바꿀 수 있다. 즉 최소 3번을 누르면 010으로 바꿀 수 있다.

 

-------------------------------------------------------------------------------------------------------------------------------------------------

 

종합하면 다음과 같다.

 

0번을 누를 수 없는 경우, 0번을 누른 경우로 나눈다.

 

1번부터 n-1번까지 순회하여 눌러야하는지 말아야하는지 체크한다.

 

현재 i번을 누를지 체크할때는, i-1번 상태가 목표로 하는 상태와 다르다면 눌러야하고 그렇지 않다면 넘어가야한다.

 

마지막 n-1번을 누를 수 없다면 불가능한 경우이고 누를 수 있다면 가능한 경우가 된다.

 

n-2번과 n-1번이 모두 목표와 다른 상태라면 n-1번을 눌러야할 것이고, 하나라도 서로 같다면 눌러도 바꿀 수 없는 상태이다.

 

둘 중 하나라도 가능하다면, 최소 횟수가 정답

 

#greedy - case by case
n = int(input())

A = list(map(int,input()))
B = list(map(int,input()))

switch = {0:1,1:0}

#0번을 누를 수 없는 경우
count1 = 0

C = A[:]

#1번부터 n-2번까지 순회하여 누를 수 있는지 없는지 체크
#i-1번이 목표로 하는 상태와 다르다면 i+1번부터는 바꿀 수 없으므로 i번을 눌러야한다.
for i in range(1,n-1):
    
    if C[i-1] != B[i-1]:
        
        count1 += 1
        
        C[i-1] = switch[C[i-1]]
        C[i] = switch[C[i]]
        C[i+1] = switch[C[i+1]]
    

#마지막 n-1번을 눌러야하는가 말아야하는가
#n-2번이 다르고, n-1번도 다르다면 n-1번을 눌러서 둘 다 바꿔줘야한다
if C[n-2] != B[n-2] and C[n-1] != B[n-1]:
    
    count1 += 1

#n-2번이나 n-1번 둘중 하나라도 서로 같다면, 눌러도 동일하게 바꿀 수 없으므로 불가능한 경우
elif (C[n-2] == B[n-2] and C[n-1] != B[n-1]) or (C[n-2] != B[n-2] and C[n-1] == B[n-1]):
    
    count1 = -1


#0번을 반드시 누른 경우
count2 = 1

C = A[:]

C[0] = switch[C[0]]
C[1] = switch[C[1]]

#1번부터 n-2번까지 순회하여 누를 수 있는지 없는지 체크
#i-1번이 목표로 하는 상태와 다르다면 i+1번부터는 바꿀 수 없으므로 i번을 눌러야한다.
for i in range(1,n-1):
    
    if C[i-1] != B[i-1]:
        
        C[i-1] = switch[C[i-1]]
        C[i] = switch[C[i]]
        C[i+1] = switch[C[i+1]]

        count2 += 1

#마지막 n-1번을 눌러야하는가 말아야하는가
#n-2번이 다르고, n-1번도 다르다면 n-1번을 눌러서 둘 다 바꿔줘야한다
if C[n-2] != B[n-2] and C[n-1] != B[n-1]:
    
    count2 += 1

#n-2번이나 n-1번 둘중 하나라도 서로 같다면, 눌러도 동일하게 바꿀 수 없으므로 불가능한 경우
elif (C[n-2] == B[n-2] and C[n-1] != B[n-1]) or (C[n-2] != B[n-2] and C[n-1] == B[n-1]):
    
    count2 = -1
    

#둘 다 불가능하다면, 바꿀 수 없는 경우
if count1 == -1 and count2 == -1:
    
    print(-1)

#둘 중 하나라도 가능하다면 최솟값이 정답
elif count1 == -1 and count2 != -1:
    
    print(count2)

elif count1 != -1 and count2 == -1:
    
    print(count1)

else:
    
    if count1 > count2:
        
        print(count2)
    
    else:
        
        print(count1)

 

이런 문제는 경험안해보면 떠올리기 힘들것 같다..

 

확실히 그리디 연습 많이 해야할듯

 

 

3. 문제2

 

30023번: 전구 상태 바꾸기 (acmicpc.net)

30023번: 전구 상태 바꾸기

 

 

4. 풀이

 

위 문제와 비슷한 아이디어로 해결할 수 있다

 

첫번째 전구의 색을 고정한 뒤에 나머지 전구의 색을 바꿔보면서 모든 전구의 색이 같은지 검사해본다

 

위 문제는 첫번째가 0 아니면 1로 두가지였지만,

 

이 문제는 첫번째 전구의 색은 R,G,B 3가지 중 하나이고 해당 상태로 첫번째 전구의 색을 고정시킨 뒤,

 

2번째, 3번째, ... , 모두 첫번째 전구의 색과 동일하도록 바꿔보고...

 

전부 동일한지를 검사해준다

 

#case by case greedy

n = int(input())

bulb = list(input())

change = {'R':'G','G':'B','B':'R'}

bulb2 = bulb[:]

answer = []

#첫번째 전구의 색을 R,G,B중 하나로 고정시키고
#두번째, 세번째, ... 모두 바꿔본 다음
#전부 같은지 검사해준다
for init in ['R','G','B']:

    count = 0
    
    #첫번째 전구의 색을 고정시키기
    while bulb2[0] != init:
        
        bulb2[0] = change[bulb2[0]]
        bulb2[1] = change[bulb2[1]]
        bulb2[2] = change[bulb2[2]]

        count += 1

    i = 1
    
    #두번째 전구부터 색을 첫번째 전구와 동일하게 바꿔본다
    while i <= n-3:

        for _ in range(3):
            
            if bulb2[i] == init: #바꾸지 않아도 처음부터 같을 수 있음
                
                break
                
            bulb2[i] = change[bulb2[i]]
            bulb2[i+1] = change[bulb2[i+1]]
            bulb2[i+2] = change[bulb2[i+2]]

            count += 1
        
        i += 1
    
    #반복문을 탈출하면, -1, -2번 인덱스의 값이 같은지 다른지만 검사해주면 됨
    #하나라도 다르다면, 전부 같은 색으로 바꿀 수 없다
    if bulb2[-1] != init or bulb2[-2] != init:
        
        count = -1

    answer.append(count)
    bulb2 = bulb[:]

if answer[0] == -1 and answer[1] == -1 and answer[2] == -1:
    
    print(-1)

else:
    
    count = 10000000000000000000000000

    for i in range(3):
        
        if answer[i] == -1:
            
            continue
        
        else:
            
            if answer[i] < count:
                
                count = answer[i]
    
    print(count)