[백준] 12927 배수 스위치(Python) - Greedy

📌 문제

강호는 전구 N개를 가지고 있다. 전구는 1번부터 N번까지 번호가 매겨져 있으며, 일렬로 놓여져 있다. 전구는 켜져있거나 꺼져있다.

강호는 모든 전구를 끄려고 한다. 강호는 전구를 켜고 끌 수 있는 스위치 N개를 가지고 있고, 스위치도 1번부터 N번까지 번호가 매겨져 있다. i번 스위치는 i의 배수 번호를 가지는 전구의 상태를 모두 반전시킨다.

현재 전구의 상태가 주어졌을 때, 모든 전구를 끄기 위해서 스위치를 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 전구의 상태가 1번 전구부터 차례대로 주어진다. Y는 전구가 켜 있는 경우, N은 전구가 꺼져있는 경우이다. 전구의 개수는 1보다 크거나 같고 1,000보다 작거나 같은 자연수이다.

출력

모든 전구를 끄기 위해서 스위치를 몇 번 눌러야 하는지 출력한다. 만약, 모든 전구를 끌 수 없다면 -1을 출력한다.

---

예제 입력1

YYYYYY

예제 출력1

1

---

예제 입력2

YNYNYNYNY

예제 출력2

2

---

예제 입력3

NNNNNNNNNN

예제 출력3

0

---

예제 입력4

YYYNYYYNYYYNYYNYYYYN

예제 출력4

4

---

📌 풀이

Code

import sys
input = sys.stdin.readline

bulbs = ['N'] + list(input().strip())   # 전구 상태 목록 (인덱스를 편리하게 확인하기 위해 앞에 N 붙이기)
N = len(bulbs)                          # 전구 개수
cnt = 0                                 # 스위치 누른 횟수
for i in range(1, N):
    if bulbs[i] == 'Y':                 # 켜져있는 전구를 만나면
        for j in range(i, N, i):        # 해당 번호 배수인 전구 상태 변경
            if bulbs[j] == 'Y':
                bulbs[j] = 'N' 
            else: 
                bulbs[j] = 'Y'
        cnt += 1                        # 스위치 한번 누름
print(cnt)

 

Solution

1. 전구 상태를 입력으로 받고, 인덱스를 편리하게 확인하기 위해 리스트 맨 앞에 원소 하나를 추가하기

 

2. 1번 전구부터 N번 전구까지 켜져 있는 전구 탐색

 

3. 켜져 있는 전구를 만나면 해당 번호 배수인 전구 상태 변경

 

4. 전구 상태를 변경 시킬 때 마다(스위치를 누를 때 마다) 카운트 1 증가

 

5. 최종 카운트 반환

---

깨달은 점

저는 처음에 이 문제의 조건을 보고 굉장히 복잡하게 생각했습니다.

켜져 있는 전구 리스트를 받은 뒤에 최대공배수를 계산해야하나? 끝까지 다 끌 수 없는 경우는 뭐지?

 

그러나!! 이 모든 것은 함정이었다는 것...

이 문제의 핵심은 바로 "모든 전구를 끌 수 없는 경우는 존재하지 않는다" 입니다.

 

생각해보면 당연한게, 자신의 배수는 자기 자신도 포함하기 때문입니다.

그러니, 앞에서부터 차례로 켜져 있는 전구 스위치를 끄다보면 결국 마지막엔 무조건 다 끌 수 있다는 거죠...

 

이 아이디어를 얻은 시점에도 사실 긴가민가 했습니다.

앞에서부터 차례로 스위치를 눌러도 정말 최적해를 찾을 수 있을까..?

 

좀 찝찝하지 않습니까?

 

찝찝한 그 느낌! 그것이 바로 그리디입니다!

Greedy Algorithm : 지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘

 

물론 그리디가 모든 경우에 최적해를 보장하지는 못하지만,

드물게 최적해를 낼 수 있는 경우도 있습니다. 이 문제가 그런 경우에 해당하죠!

 

이 문제에서 그리디 알고리즘이 최적해를 찾을 수 있는 이유는 특정 전구의 상태를 변경하는 스위치가 고유하게 그 전구의 상태만 반전시키기 때문입니다.

i번 스위치는 i의 배수인 전구들만 조작하며, 이 과정에서 특정 전구가 여러 번 상태를 반전하게 되지만, 결과적으로 마지막에 이 전구가 꺼지도록 조작됩니다.

 

그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하면서 진행하기 때문에,

전구를 모두 끄기 위해 필요한 최소한의 스위치 조작 횟수를 보장할 수 있습니다.

 

앞으로는 각 단계마다 지역 최적해를 찾는 문제,

즉 문제를 더 작게 줄여나가는 형태가 보이면 그리디를 떠올려야겠습니다!