안녕하세요,
재재입니다.
BOJ 12907 동물원 문제 풀이입니다.
BOJ 12907 동물원
(1) 문제 설명
분류 : math, 조합론
출처 : https://www.acmicpc.net/problem/12907
(40 이하) N 개의 숫자가 주어집니다.
토끼 및 고양이에게 질문을 할 수 있으며,
자신보다 큰 토끼 혹은 고양이가 몇 인지 알려줍니다.
이때, 가능한 경우의 수 출력해주면 됩니다.
(2) 풀이 도출
토끼인지, 고양이인지 알 수 없습니다.
다만, 일관성이 있어야 합니다.
숫자가 등장한 횟수를 세서 2개가 넘으면 불가능한 경우입니다.
또한, 누적된 숫자는 가장 낮은 숫자부터 내림차순이어야 합니다.
그 외의 정보는 가능한 경우의 수를 직접 나열해보면 쉽게 알 수 있습니다.
여기서 파악해야 하는 정보는, 등장한 횟수가 2개인 경우와 1개인 경우에 대한 처리입니다.
2개인 숫자는 독립 사건으로 x2 가 가능하며,
1개인 경우가 존재한다면 x2 를 하면 됩니다.
(3) 정답 코드
BOJ 12907 동물원