728x90
<<다시 풀어보기>>
문제 링크
https://www.acmicpc.net/problem/2138
TIL
- 그리디 알고리즘이지만, 무작정 푸는 것이 아닌 경우의 수를 나눠서 각 경우의 수를 그리디 돌려야하는 문제 !!
- 이런 문제 유형도 있으니 항상 고려하기
- 1 <> 0 반전하는 쉬운 방법
- value = 1-value 하면 됨 ( https://taltal.tistory.com/100 참고 )
- 혹은 XOR 연산으로 가능 (^)
- 혹은 NOT 연산으로 가능 (not) > 대신 bool 타입으로 바뀜
- 시간 초과에 대해서
- 그냥 bfs로 짠 코드는 최대 3의 100,000번 거듭제곱이므로 시간 & 메모리 초과
- 실제로는 메모리 초과 뜸
- 거듭 제곱의 지수가 100이상이면 무조건 안됨 !!!! 밑수가 2여도 안됨.
- 참고: https://ourcalc.com/%EA%B1%B0%EB%93%AD%EC%A0%9C%EA%B3%B1-%EA%B3%84%EC%82%B0%EA%B8%B0/
- 그냥 bfs로 짠 코드는 최대 3의 100,000번 거듭제곱이므로 시간 & 메모리 초과
- 종료 조건을 어떻게 설정하지 ? > 불가능하면 -1을 반환해야함
- 다 돌고나서도 타겟 상태와 다르다면 -1을, 아니라면 cnt를 반환
- 왜 그리디 알고리즘을 사용하는 것이 적합한가?
- 전구를 스위치하는 순서는 중요하지 않음 !!! 누르냐 아니냐 여부가 중요
- 로컬 최적해가 글로벌 최적해를 보장: 전구의 현재 상태가 목표 상태와 다를 때 스위치를 눌러 상태를 변경하는 것이 그 순간에서 최선의 행동입니다. 이 결정은 그 이후의 전구들에게 영향을 미치지만, 순차적으로 스위치를 처리함으로써 최종적으로 원하는 결과를 얻을 수 있습니다.
- 뒤돌아갈 필요가 없음: 한 번 스위치를 누른 이후에는, 해당 스위치를 다시 고려할 필요가 없습니다. 이는 각 스위치의 누름이 그 이후의 전구들에 대한 결정에만 영향을 미친다는 사실 때문입니다. 즉, 한 번 결정이 내려지면, 그 결정은 최종적으로 전체 문제 해결에 기여합니다.
- 문제의 독립성: 각 스위치를 누르는 결정은 그 순간의 전구 상태에만 기반하고 있으며, 각 결정은 서로 독립적으로 최적의 선택을 제공합니다. 이는 전체 문제를 더 작은 문제로 나누고 각각을 독립적으로 해결할 수 있음을 의미합니다.
- 연쇄 효과: 스위치를 누르는 행위는 연속된 세 전구에 영향을 미치며, 이러한 연쇄 효과를 고려하여 각 스위치를 누를지 말지 결정합니다. 스위치를 누름으로써 발생하는 연쇄적인 상태 변화를 계산에 포함시키는 것이 그리디 알고리즘의 핵심입니다.
- 스위치를 왜 한 번만 누른다고 가정하는가?
- 한 개의 스위치를 여러 번 누를 수 있지만, 실제로는 그렇게 할 필요가 없습니다. 스위치를 한 번 누르면 연결된 전구들의 상태가 반전됩니다. 같은 스위치를 두 번 누르면 전구들의 상태가 원래대로 돌아오기 때문에, 스위치를 두 번 누른 효과는 아무 것도 하지 않은 것과 같습니다. 이러한 이유로, 각 스위치를 최대 한 번만 누르는 것을 고려하면 충분합니다.
# BFS -> 최소 횟수
# 이 문제는 BFS가 아니라 그리디 사용해야함!!!!
n = int(input())
current = list(map(int, list(input())))
will = list(map(int, list(input())))
def click(c_grid, i):
global n
temp = c_grid.copy() # 필수 !!!! 안하면 c_grid가 그대로 수정됨
for bulb in (i-1, i, i+1):
if 0<=bulb<n:
temp[bulb] = not temp[bulb]
return temp
def find_first():
global current
global will
for i in range(n):
if current[i] != will[i]:
return i
def solve():
cnt = 0
while True:
if current == will:
print(cnt)
break
i = find_first()
for bulb in (i, i+1, i+2): # click
if 0<=bulb<n:
current[bulb] = not current[bulb]
cnt += 1
return cnt
if __name__=="__main__":
solve()
- 이렇게 하면 시간초과 발생 + 하나의 스위치를 여러 번 누르게 됨
- -1을 반환할 수 있는 조건을 설정해두지 않았기 때문에 불가능한 경우 무한 루프를 돌게 됨
- 참고할 만한 파이썬 코드
[ 문제 풀이 방법 ] - Greedy 참고 !!!
- 하나의 버튼을 누르면 양옆에 모두 영향을 받기 때문에 이를 고려해야 함
- 따라서 i-1번째 상태를 기준으로 하고, 이를 바꾸기 위해 i번째 스위치를 누르도록 동작 실행
- 즉, 1번째 전구는 누르거나 누르지 않거나로 나뉘게 됨
- 1번째를 누르지 않고 전체 전구를 순회한 뒤 답이 나오면 그대로 반환
- 답이 나오지 않는다면 1번째를 누르고 다시 전체 전구를 순회하는 방법으로 한 번 더 실행
- 이때 중요한 거 !!!!!!! 배열을 복사해두고 사용해야 함 >> 그렇지 않으면 초기화 불가능
- 1번째를 누르지 않고 전구 순회한 뒤에 답이 아니면 1번 누르는 거로 해도 되지 않나? >> 내 처음 생각
- 1번째를 누르면 2번째 전구에도 영향이 가고, 그러면 그 뒤에 누르는 조합이 바뀔 수도 있으므로 아예 달라짐
- 첫 번째 전구를 누른다면 cnt +1 해줘야 함 !!!!
Code
n = int(input())
bulbs = list(map(int,list(input())))
target = list(map(int,list(input())))
def press_first(current):
cnt = 0
if target==current:
return cnt
for i in range(1,n):
if current[i-1] != target[i-1]:
click(i)
cnt += 1
return cnt if target == current else -1
def press_second(current):
cnt = 0
if target==current:
return cnt
cnt += 1
current[0] = 1-current[0]
current[1] = 1- current[1]
for i in range(1,n):
if current[i-1] != target[i-1]:
click(i)
cnt += 1
return cnt if target == current else -1
def click(i):
if i==0:
current[0] = 1-current[0]
current[1] = 1- current[1]
elif i==n-1:
current[i] = 1- current[i]
current[i-1] = 1- current[i-1]
else:
current[i] = 1-current[i]
current[i-1] = 1-current[i-1]
current[i+1] = 1-current[i+1]
if __name__ == "__main__":
current = bulbs.copy()
ans = press_first(current)
if ans > 0:
print(ans)
else:
current = bulbs.copy()
print(press_second(current))
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 1253번: 좋다 (0) | 2025.03.21 |
---|---|
[BOJ] 3273번: 두 수의 합 (two-pointer) / sliding window, hash set (0) | 2025.03.20 |
[BOJ] 2631번: 줄세우기 (LIS) / LIS 알고리즘 문제 (0) | 2025.03.20 |
[BOJ] 1967번: 트리의 지름 (DFS) (0) | 2025.03.19 |
[BOJ] 2573번: 빙산 (BFS/DFS) (0) | 2025.03.18 |