[백준 / BOJ] 17349 1루수가 누구야

문제

출처 : www.acmicpc.net/problem/17349

17349번: 1루수가 누구야

총 9명의 선수중 1루수가 누구인지 찾는 문제이다.

9개의 줄에거쳐 각 선수가 주장을하는데 무조건 한명은 거짓말을 하고있다.

선수들의 주장은

1 A: 선수 A가 1루수이다.

0 A: 선수 A는 1루수가 아니다.

로 나타난다.

(단, 1루수를 찾을수 없으면 -1을 출력한다.)

풀이

"한명의 선수가 거짓말을 하고있다." 는 조건이 있으니,

1번 선수가 거짓말을 할때, 2번 선수가 거짓말을 할때, 3번 선수가 거짓말을 할때...9번 선수가 거짓말을 할때 로 나눠서 완전탐색을 돌린다.(즉, n번 선수가 거짓말을 하고있다고 가정을 하고 탐색을 한다.)

이때, 1루수를 찾으면 출력하고 종료하고 9번선수가 거짓말을 할때까지 1루수를 찾지 못하면 -1을 출력한다.

예를들어,

 

1 2

0 2

1 2

1 2

1 2

0 4

0 4

0 4 

0 4

의 경우, 2번선수가 거짓말을 하고있다면,

0 2 -> 1 2 로 바뀌게되고, 모든 선수가 2번이 1루수라고 증언하므로 2번이 1루수 이다.

 

반례를 조심해야했는데..(이것때문에 틀렸었다)

0 1

0 1

0 1

0 2

0 2

0 2

0 3

0 3

0 3

의 경우

1루수는 4 5 6 7 8 9 가 될수있다. 따라서 -1을 출력해야한다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/17349%201%EB%A3%A8%EC%88%98%EA%B0%80%20%EB%88%84%EA%B5%AC%EC%95%BC/main.cpp

devxb/JJUNalgo