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

욥·2025년 7월 7일

백준 알고리즘

목록 보기

192/325

2가지 경우를 시도하는 그리디_251020

최적 부분구조 그리디

: 전체 문제를 작은 문제부터 최적화해서 구하는 문제이고,
지금 문제의 경우, 특정 전구 한개 한개를 어떻게 변경하는 것이 최고의 선택일까?? 를 생각하는 문제이다.

왜 그리디냐?_251021

: 그리디는 전체의 최적화값을 구하기 전에 작은값부터 먼저 최적값을 구해나가는 과정인데,
idx 스위치를 최대 누를 수 있는 회수는 1번이다. 2번 누르면 바보다. 2번 누르면 그대로이다.
즉 브루트포스로 생각하면 2의 10만승이므로, 브루트 안되고,

idx 버튼을 누르냐? 누르지 않는냐? 를 통해서
문제의 목표값에 도달하는 최적값이다.
idx 버튼을 누르지 않더라도, idx + 1 버튼을 통해서
idx 전구가 변경될 수 있다.
idx 버튼을 누르더라도 idx + 1버튼을 통해서 idx 전구가 변경될 수 있다.

=> 즉 idx 버튼을 누른 경우와 idx 버튼을 누르지 않는 방법을 진행하면, idx + 1 버튼 입장에서 누를까? 누르지 말까?
즉 다음번에 대한 최적값 2가지 경우에 대해서 정할 수 있다.

그리디의 최적부분 구조는 매순간 최적의 해를 만들어 나가는 것이다.

==> 결론 첫번째 버튼을 누르는 방법과 첫번째 버튼을 누르지 않는 방법으로 코드 작업하자.

나의 생각.

idx 전구가 비교 대상이 달라서 idx를 변경하는 방법은
1) idx를 누르거나 ,
2) idx를 누르지 않으면서, idx + 1을 누르는 것이다.
위의 생각을 모든 전구에 대입해보면 되지 않을까? 란 생각을 함.
-> 이게 가능한 이유는
1) 나를 누르지 않더라도 뒤의 스위치를 누르는 방법이 최소 카운딩이 될 수 있다.
2) 나를 누른 경우가 최소 카운팅이 될 수 있다.

반례

예제 입력에 반례를 하는 것보다 해결전략을 가지고 밀어붙이는
것이 그리디이다.

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

행렬과 아주 조금 유사한 듯 하지만, 생각을 더 해야 한다.
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번을 누르기만 하면된다.