[백준 2138번] 전구와 스위치(C++)

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

 

여러가지 상황을 시도하고 규칙성을 찾아내는 것이 관건인 문제이다. 관건은 서로 영향을 줄 수 있는 스위치들이 엮여있기 때문에 모든 경우의 수를 해보는 것이 가장 간단하지만 시간초과가 날 것이다.

 

먼저 서로 영향을 끼치는 관계를 그림으로 나타내보자

 

 

무엇을 의미하는지 잘 모르겠다..

그러나 일반적으로 어떤 방식을 사용하던 스위치는 결국 켜거나 놔두게 될 것이다. 한번 1번 스위치를 켰다고 가정하자. 

그렇다면 1,2번 전구가 켜졌을 것이다. 

 

 

그리고 이제 2번 스위치를 켤지 말지 결정해보자. 어라? 여기서 1번을 향하고 있는 스위치가 단 한개이다..!

즉 1번은 이제 내 마음대로 조절할수가 있게 되었다. 

 

만약 목표로하는 타겟의 1번이 켜져있다면 2번을 누르지 않을 것이고 1번이 꺼져있다면 2번을 누를 것이다. 2번 타겟의 대한 것을 3번에서 확인한다.

 

즉, i - 1의 대한 정보를 i 번째에서 결정한다. 그리고 마지막 전구를 조절할 수 있는 것은 결국 자기 자신 뿐이다. 그러므로 만약 마지막 전구가 i - 1을 결정했는데 안맞는다면 타게에 도달할 수 없는 경우가 된다.

 

그런데 이것이 최적해일까?

 

이것은 순서대로 스위치를 켤지말지 결정하는 그리디 방식이다. 그리디 방식을 사용하려면 지금의 선택이 가장 최적으로 이후에 영향을 미쳐서는 안된다. 그리고 i - 1번을 바꾸기 위해 i, i + 1 번은 고려하지 않는 것이 불안해보일 수 있다.

 

하지만 이 문제는 확실히 이 것을 만족한다. 왜냐하면 지금 i - 1이 타겟과 다른데 지나친다면 i - 1을 이제 절대로 바꿀 수 가 없기 때문이다.

 

무작정 시도하지 않고 영향도의 대한 것을 그림으로 나타낸 후 천천히 진행해야 풀 수 있는 문제였다.

개인적으로 난이도를 더 올려야한다고 생각하는 문제