[백준 그리디] 2138 전구와 스위치

🥕 [ 백준 2138 ] 전구와 스위치

문제 링크

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

2138번: 전구와 스위치

 

🍒 문제 분석

N개의 전구가 있다. i번 스위치를 누르면 i-1, i, i+1 세개 전구에 불이 들어오거나 또는 꺼진다.

단, 1번째 스위치를 누르면 1과 2만 작동하며, 마찬가지로 마지막 N번째 스위치를 누르면 N-1과 N만 작동한다.

최소한의 동작으로 전구를 주어진 상황에서 목표하는 상황까지 도달한다고 할 때, 몇번의 동작을 거쳐야 하는지 구해야 하는 문제.

 

input) 000

output) 010

 

010 상태를 나타내기 위해서는 각각의 전구의 버튼을 누를 것인지, 누르지 않을 것인지를 결정하면 된다.

 

굳이 동일한 스위치를 두 번 누를 필요는 없다. 누르면 켜지고 다시 누르면 꺼지기 때문에, 이는 불필요한 동작의 낭비가 되는 것이다.

 

따라서 for문으로 각 전구를 누를 것인지 말 것인지에 대해서 단 한 번만 흝으면 되겠다.

 

(단, 누를지 말지에 대해 이미 결정을 내린 이전의 전구로는 다시 돌아갈 수 없다. )

 

🥑 코드

import copy
def turn(i, mylist):
    # i가 0 일 때,
    if i == 0 :
        mylist[i+1] = not mylist[i+1]
        mylist[i] = not mylist[i]

    # i가 N-1 일 때,
    elif i == N-1 :
        mylist[i-1] = not mylist[i-1]
        mylist[i] = not mylist[i]
        
	# 일반적인 i
    else:
        mylist[i+1] = not mylist[i+1]
        mylist[i] = not mylist[i]
        mylist[i-1] = not mylist[i-1]

def sol(start_on,start_off):
	# start_on 일 때와 start_off 일 때
    for i in range(2):
        start = start_on if i==0 else start_off

        for j in range(1,N):
            if start[j-1] != end[j-1]:
                cnt[i] += 1
                turn(j,start)
                
        # 값이 안나온다면 100001 을 넣음 ( return에서 min을 쓰기 위해 )
        if start[-1] != end[-1]:
            cnt[i] = 100001
    
    if min(cnt[0],cnt[1]) == 100001:
        return -1
    else : return min(cnt[0],cnt[1])

N = int(input())
start = [True if i == '1' else False for i in input()]
end = [True if i == '1' else False for i in input()]

# 0 번째 전구가 켜진 start_on
start_on = copy.deepcopy(start)
turn(0,start_on)

# 0번째 전구를 키지 않은 start_off
start_off = copy.deepcopy(start)

# start_on, start_off
cnt = [1,0]

print(sol(start_on,start_off))

🍓 내 해결 과정

전략은 문제 접근에서 쓴 것과 동일하다.

 

1. for 문 을 돌고, 각 전구를 하나씩 확인한다.
   
   어떻게 확인하는지가 문제인데,
   start 배열과 end 배열의 i-1 번째 항이 매치되는가를 확인하면 된다.
   
   i-1번째 항이 매치되지 않는다면, i번째 전구의 스위치를 누른다.
   그 뒤에는 i-1번째 항을 다시 볼일이 없기 때문에, 각 전구를 한번씩만 확인할 수 있게 된다.
   
   
2. 문제는 0번째 항 같은 경우 i-1 번째 전구가 없다는 것인데, 따라서 케이스를 2 개로 나눈다.
   0번째 스위치를 눌렀을 때와 누르지 않았을 때.
   이렇게 케이스를 나누면, 0번째 스위치를 눌렀을 때의 최적의 동작 수와 0번째 스위치를 누르지 않았을 때의 최적의 동작 수를 모두 다 고려할 수 있게 된다.
   
   
3. 답은 4 가지 중 하나로 리턴할 수 있다.
   a. 1번째와 2번째 케이스 모두에서 end 배열을 만들 수 없을 때
   b. 1번째 케이스 에서만 end 배열을 만들 수 없을 때,
   c. 2번째 케이스 에서만 end 배열을 만들 수 없을 때,
   d. 1번째 케이스와 2번째 케이스 모두에서 end 배열을 만들 수 있을 때 

 

🌽 다른 사람 코드

구글링을 해보니, 사람마다 아이디어는 같지만 코드는 각양각생이다.

 

🍉 깨달은 점 및 정리

1. deep copy와 shallow copy의 활용

start에다가 배열을 받아서 deep copy로 케이스 2개에 대한 배열을 만든 뒤,

for문을 돌릴 때, start 에다가 각 배열을 받아서 shallow copy를 활용해 각 케이스에 대해 체크해주었다.

이렇게 하니 코드가 start 변수 하나로 깔끔해져서 보기 좋았다.

 

2. 찾을 수 없을 때 cnt에 -1 대신 100001 넣기

cnt에 -1 대신 100001을 넣으니 케이스 두 개 중 값이 안나온 케이스를 배제할 때, 그리고 최적이 아닌 케이스를 배제할 때

min 함수 한번만 써주면 돼서 코드가 매우 깔끔해졌다.

그리고 두 케이스 모두 값이 없다면 if 구문을 통해 100001 과 같은지 확인하고 같을 경우 -1만 프린트 해주면 된다.

코드가 매우 보기 좋았다.

 

3. 카드 뒤집기 문제, 전구 스위치 켜기 문제

그리디 단골 유형 중 하나인듯 하며, 비슷한 풀이가 적용되는 모양이다.

이번에 하나 알았으니 다음에도 또 쉽게 풀 수 있을 것 같다.