잘못된 이유 , 반례
https://www.acmicpc.net/board/view/46227
나의 알고리즘 문제 해결 전략
- 각 파티에 대해서 진실아는 친구가 있다면 해당 파티에 있는 모든 사람들에 대해서 같은 그룹으로 만들려고 했따.
- 예를 들어 진실 아는 친구는 1,2,3,4 인데
9번을 순회하는 도중에 진실과 같은 그룹에 있는 파티는
2 1 2 번 / 2 2 6번 / 2 3 10번 이므로
과장해서 말할 수 있는 파티는
1 7 번 / 1 8 번/ 2 7 8 번 / 1 9 번 /
=> 총 4개이다.
생각치 못한 부분이 있다.
하면서 내가 위의 그림을 통해서 오잉 그러면 밑에서 부터 채워진다?
그러면 이러한 상황이 잏지 않을까? 를 생각해야 한다.
: 맨 위에는 진실아는 친구 없고, 맨 마지막 파티에 진실 아는 친구 1명 있고, 그 파티에 3명 있는데,
그 3명의 친구 와 겹쳐 있는 이전 파티에 진실 모르는 친구들이 또 같이 있는 경우에 대해서 생각해야 한다....
1 6
2 4 5
2 3 4
2 5 6
// => 이라고 한다면??
2 5 6 에 의해서 5 6번은 진실 알게 되고,
그로 인해 4 5번 도 알게 되어서 4 5 6 알게 되고
그러면 3 4 에서도 알게 되어서 결론적으로 3 4 5 6 번친구가
진실을 알게 된다는 것이다.
=> 즉 알고리즘 해결 전력이 잘못됨을 증명한다.
결론
: 코드 작성하기 전 나의 문제 해결 전략 빈틈이 없는지 생각해야 한다.
회고
- 위의 해결 전략은 각 파티에 대한 기준이 아니라, 2번째 줄에 입력되는 진실된 사람을 기준으로 해서 생각하게 된 방법이다.
물론 잘못된 해결 방법이라고는 할 수는 없다.
하지만, 위의 내가 반례를 든 것처럼 오답이 발생한다.
결론
: 문제를 읽었을 때, 한 그룹의 파티에 대해서 과장해서 이야기 할 수 있는냐? 를 기준으로 할 수 밖에 없다. 왜냐하면 문제에서 그렇게 제시를 했기 때문이다.
- 각 파티를 그룹으로 만들어 놓고, 진실된 사람들 과 vs 를 하면서 과장된 이야기를 할 수 있는지를 카운팅하면 된다.
🔥🔥🔥