2138. 전구와 스위치_아이디어 문제.

욥·2025년 7월 7일

백준 알고리즘

목록 보기

192/270

아이디어 제시 못하면 틀림.

행렬과 아주 조금 유사한 듯 하지만, 생각을 더 해야 한다.
https://velog.io/@kwt0124/1080.-%ED%96%89%EB%A0%AC

참고 블로그

https://howudong.tistory.com/93#article-1--%EB%AC%B8%EC%A0%9C-%EC%9D%B4%ED%95%B4-%EB%8B%A8%EA%B3%84

https://astrid-dm.tistory.com/429

250708 맞음

문제 해결 전략

: 최소값을 구하는 문제이고, 뺑뺑이를 돌리기 보다 구현하면 될 듯하다.
-> 그리디 인가?? 명제를 만들자.

어떻게 최소값을 구할 수 있을까? 관점을 가지고 진행하자.
me 와 target 값이 있다.
me의 i번 이 target의 i와 다르다고 하자.
-> 여기서 i가 다르다고 표현한다.

명제

: i번 전구가 다르면 2개의 경우가 있다.
i번 스위치를 누르거나, i + 1번 스위치를 누르거나.

1) i가 다르면 i번 스위치를 눌러서 i번 전구 동일하게 하는 경우가 있다. 그런데 이때는 i+1 번 전구도 변경된다.
그런데 i + 1번 전구 입장에서는 아니 나를 왜 뒤집어! i번 누르기 전에 나는 동일했다고 !!!
그래서 어쩔수 없이 i + 1번도 다르기 때문에 i + 2번 스위치를 눌러야 한다.
그런데 i + 2번 스위치를 누르고 싶은데 i + 2번은 동일하다...
->>> 느낀 점 : 오잉???!!
: 지금 이렇게 진행하는 것은 답을 구할 수 없는 시퀀스이다.
나를 기준으로 해서 다음 전구에 영향을 준다.
-> 그리고 이런식으로 하면 i번 뒤집었다가 i+1이 일치하지 않아서 i+1번을 누르게 되는 상황이 오면 최소값이 아니게 된다.

2) i가 다르면 i + 1번 스위치를 눌러서 i번과 i+1 번을 전구 변경할 수 있다.
그런데 i + 1번 전구가 다르다. 그럼 i + 2번 스위치를 누르면 된다. (i + 1번 전구가 다르지 않다면 i + 1전구 누르지 않아도 된다.)
i + 2번 전구가 다르면 i + 3번 스위치를 누르면 된다.

결론

: i번이 다르면 i + 1을 누르자.
비록 i + 1이 다르더라도 i + 1을 누르지 않고, i + 2를 눌러서 i 한테는 피해가 되지 않게 되고, 이렇게 진행하면 최소값을 구하거나 또는 -1이 출력된다.

문제가 있다.

위의 명제를 가지고 머릿속으로 입력 예제를 풀어보자.
위의 명제로 입력 예제 1번을 진행하면 답을 구할수 없다.

어떻게 할 것인가?

: 0번이 다르고 같고 무관하게 0번 스위치를 누르거나 누르지 않는 상태 둘로 나누어서 진행하자.

왜냐하면 최소값을 구하는 건데
만야게 0번을 눌러서 1번도 변경되었는데, 나이스 하게 0번과 1번 전구 동일하네??? 그럼 땡큐다! 그리고 2번은 그대로다.
만약에 0번을 누르지 않고, 1번을 누르게 되면, 아니 2번 전구도 변경되잖아... 그런데 2번이 다르다... 어떻게 될지
그럼 2번을 누르지 말고, 위에서 구한 명제 를 통해서
3번을 누르기만 하면된다.