서론
그리디 문제입니다.
다른 분들의 도움을 받아 해결하였습니다.
그 분들은 어떻게 풀이가 떠올랐는지 대단하네요..
난이도
골드 5
문제
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 128 MB |
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풀이
이 문제는 두 가지의 상황을 주어 문제를 해결해야 합니다.
- 첫 번째 스위치를 누르지 않은 경우
- 첫 번째 스위치를 누른 경우
i번째 스위치를 누르면, i - 1, i, i + 1번째 전구들의 값이 모두 변경됩니다.
그 이후 i + 1번째 스위치를 누르면, i, i + 1, i + 2번째 전구들의 값이 모두 변경됩니다.
따라서, i번째 전구의 값을 변경할 수 있는 최종 위치는 i + 1 입니다.
예제를 예시로 들어보겠습니다.
a = 000, b = 010
첫 번째 스위치를 누른 경우:
a = 110 (첫 번째 전구가 b와 다르기에 두 번째 스위치도 눌러야 한다.)
a = 001 (두 번째 전구가 b와 다르기에 세 번째 스위치도 눌러야 한다.)
a = 010, a == b
첫 번째 스위치를 누르지 않은 경우:
a = 000 (첫 번째 전구가 b와 같기에 두 번째 스위치를 누르지 않는다.)
a = 000 (두 번째 전구가 b와 다르기에 세 번째 스위치를 눌러야 한다.)
a = 011, a != b
첫 번째 스위치를 누르는지에 따라 두 번째 스위치에서 첫 번째 전구를 보고 누를지 말지 결정을 하고, 이에 따라 세 번째 스위치를 누를지 말지 결정을 하게 됩니다.
따라서, 첫 번째 스위치를 누르는지 안누르는지에 따라 그 뒤의 모든 경우가 바뀌게 되고,
이는 결국 첫 번째 스위치를 누르는가가 핵심 요소가 됩니다.
코드
def turn(): # 스위치를 키고 끄는 함수
tmp = a[:] # a의 복사본
cnt = 0 # 스위치를 몇 번 켰는지
for i in range(1, n): # 두 번째 전구부터 시작
if tmp[i - 1] != b[i - 1]: # 이전 전구의 값이 다르다면
cnt += 1 # 스위치 on
for j in range(i - 1, i + 2): # 이전 전구, 자기 자신, 다음 전구의 값을 변경
if j < n: # 인덱스 에러 방지
tmp[j] = 1 - tmp[j] # 입력을 int형으로 받았기 때문에 1 - 0으로 0과 1을 바꿔줌
return cnt if tmp == b else 100001 # 탐색 후 두 배열이 같다면 cnt, 아니면 임의의 최댓값 반환
n = int(input())
a = list(map(int, input())) # 문자열을 int형으로 변경하여 배열에 담음
b = list(map(int, input()))
ans = turn() # 첫 번째 스위치를 누르지 않은 경우의 값
a[0] = 1 - a[0] # 첫 번째 스위치를 누른 경우(첫 번째 전구와 두 번째 전구의 숫자 변경)
a[1] = 1 - a[1]
ans = min(ans, turn() + 1) # 더 적은 횟수로 a와 b를 동일하게 만든 경우의 스위치를 누른 횟수
print(-1 if ans == 100001 else ans) # a와 b가 같아질 수 없을 경우 -1, 아니라면 횟수 출력실행 결과
