[백준 2138번] 전구와 스위치 (Python) (-1e9, 1e9로 최솟값, 최댓값 설정하기)

> 파이썬, 그리디 알고리즘

 

 

 

 

 

📖 문제 : 전구와 스위치 (Python)

 

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

 

 

예제 입력 1

3
000
010

예제 출력 1 

3

 

 

 

내 코드

def change(first, target):
    first_copy = first[:]
    cnt = 0
    for i in range(1, N):

        if first_copy[i - 1] == target[i - 1]:
            continue

        cnt += 1
        for j in range(i - 1, i + 2):
            if j < N:
                first_copy[j] = 1 - first_copy[j]

    if first_copy == target:
        return cnt
    else:
        return 1e9


N = int(input())
first = list(map(int, input()))
target = list(map(int, input()))

# 0번째 전구 끈 경우
res = change(first, target)

# 0번째 전구 킨 경우
first[0] = 1 - first[0]
first[1] = 1 - first[1]

res = min(res, change(first, target) + 1)

if res != 1e9:
    print(res)
else:
    print(-1)

 

 

 

Point ! ⭐️ 

• 이 문제 풀이법은 다른 사람 것을 참고 했는데요 !
  그리디 알고리즘인 만큼 아무리 입력값이 길어도 그 문제마다의 고유한 방법만 알아내면 다 풀 수 있는 건데 !
  
  일단, 맨 처음 0번째 전구를 키고 시작하는지, 아닌지에 따라 결과값이 달라집니다. 
  왜냐하면 하나의 전구를 켜도 왼쪽 오른쪽 전구의 상태가 바뀌기 때문에 그 두가지의 경우를 생각해서 그 두개 상태로 구한 값 중 최솟값을 출력해 줍니다. 
  
  우선 0번째를 키는지, 아닌지에 따라 0번째의 전구 상태를 변경해준 후,
  1번째 부터는 바로 전(0번째) 의 전구를 만들어야하는 전구의 모습과 비교하여 켜야하는지 아닌지에 따라 끝까지 탐색하여 횟수를 늘려주면 됩니다. 
  
  예를 들면,
  초기 값 (00000) / 결과값 (01110) 이라고 하면
  1) 0번째 전구를 키는 경우 (00000 -> 11000) 횟수 + 1
  1- 1) 결과값 0번째를 보고 1번째를 킨다(상태를 변경한다). (결과값 0번째 전구 0이므로) 횟수 + 1
         11000 -> 00100
  1- 2) 결과값 1번째를 보고 2번째를 끈다(상태를 변경한다). (결과값 1번째 전구 1이므로) 횟수 + 1
         00100 -> 01010
  1- 3) 결과값 2번째를 보고 3번째를 끈다(상태를 변경한다). (결과값 2번째 전구 1이므로) 횟수 + 1
         01010 -> 01101
  1- 4) 결과값 3번째를 보고 4번째를 끈다(상태를 변경한다). (결과값 3번째 전구 1이므로) 횟수 + 1
         01101 -> 01110
  
  이렇게 해서 횟수는 5번 !!
  
  2) 0번째 전구를 끄는 경우 (00000) 횟수 0
  2- 1) 결과값 0번째를 보고 1번째를 놔둔다(상태를 변경하지 않는다). (결과값 0번째 전구 0이므로) 횟수 0
         00000 -> 00000
  2- 2) 결과값 1번째를 보고 2번째를 킨다(상태를 변경한다). (결과값 1번째 전구 1이므로) 횟수 + 1
         00000 -> 01110
  
  이렇게 횟수는 1번 !!
  
  두가지 경우 중 최솟값은 2번 경우로 1번이면 결과값처럼 만들 수 있다. 

 

• 파이썬에서 변수를 최댓값과 최솟값으로 사용해야할 때,
  최댓값 num = 1e9
  최댓값 num = -1e9 
  로 설정해주면 됩니다. 무한(INF)의 값으로 1e9를 이용할 수 있습니다. 

 

 

 

 

 

백준

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

2138번: 전구와 스위치