정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.
* 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) * 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) * 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다.
숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.
예) 영수가 324를 갖고 있으면 429는 1 스트라이크 1 볼이다. 241은 0 스트라이크 2 볼이다. 924는 2 스트라이크 0 볼이다.
영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
* 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다.
아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.
현재 민혁이와 영수는 게임을 하고 있는 도중에 있다.
민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다.
이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.
영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다.
그러므로 영수의 답들에는 모순이 없다.
민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때
영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.
첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.
첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.
4
123 1 1
356 1 0
327 2 0
489 0 1
2
처음 프로그래밍을 배울 때 예제로 많이 등장하는 야구 게임이다. 다만, 답을 맞추는 게 아니라 가능성이 있는 답의 개수를 출력한다는 차이가 있는 것 같은데... 결과적으로 기존에 풀었던 야구 게임을 조금 더 어렵게 만든 것 같다.
일단 기본적으로 각 자리수에 후보군으로 [1 ~ 9]인 리스트가 존재하고 해당 자리에 값이 확정되는 경우 해당 리스트를 해당 값을 제외한 나머지를 제거하고 정답이 아닌것을 확정할 수 있는 경우에도 후보군에서 제외하면 결과적으로 후보군 리스트의 크기(Size)를 이용해 순열로 해결하면 될 것이라고 생각했다. 그런데 종이에 쓰면서 생각을 하는데 계속 중간에 막히고 있다.
그리고 예제에서 324와 328이 최종 후보라고 했는데 왜 9가 제외된 건지 전혀 이해가 되지 않는다.
그래서 질문으로 올려놨는데 제대로 답변이 올지는 모르겠다. 답변 받고 나서 다시 생각해봐야지....
2018-10-05 수정)
답변은 여전히 안 왔고 그동안에 자기소개서 쓰고 포트폴리오 준비하느라 전혀 진행 못하다가 오늘 다시 확인한다고 들어가서 읽어보니 이제야 이해하 되네요. 앞에서 3, 2, ? 인 상태가 되었는데 마지막 4, 8, 9에서 9가 만약 맞는 숫자라면 스트라이크가 되어야 하는데 1 볼이므로 9는 제외되고 4와 8이 후보가 되는 거였네요. 이제 진행할 수 있을 듯 합니다.
2018-10-16 수정)
드디어 졸업작품 전시까지 끝나고 좀 쉬다가 이제 다시 알고리즘을 확인하고 있는데 지금까지 생각했던 후보군에서 해당 값을 제거하는 방식은 적절하지 않은 것 같습니다. 못할것 까진 없겠지만 비효율적일 수 있겠습니다. 그리고 문제가 초등학교 문제인 것을 생각하면 단순 반복문으로 처리하는게 답인 것 같습니다. (문제 이해를 위해 다음 사이트를 참고했습니다. 이동)
