[백준/12907번] 동물원 - G5/Python

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

문제

동물원에 동물이 N마리 있고, 1번부터 N번가지 번호가 매겨져 있다. 이 동물원에 동물은 토끼나 고양이밖에 없고, 모든 동물의 키는 다 다르다.

수빈이는 토끼와 고양이를 구분할 수 없지만, 토끼와 고양이와 대화를 할 수 있다!

수빈이는 모든 동물에게 다음과 같은 질문을 했다.

"너랑 같은 동물 중에서 너보다 키가 큰 동물은 몇 마리야?"

모든 토끼는 자신보다 키가 큰 토끼의 수를 말해줬고, 모든 고양이도 자신보다 키가 큰 고양이의 수를 말해줬다.

모든 동물의 대답이 주어졌을 때, 각 대답을 어떤 동물이 했는지 알아내려고 한다. 가능한 조합의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동물의 수 N (1 ≤ N ≤ 40)이 주어진다.

둘째 줄에는 각 동물의 대답이 주어진다. 대답은 0보다 크거나 같고, 40보다 작거나 같은 정수이다.

풀이

n = int(input())
info = list(map(int, input().split()))
max_val = max(info)
if max_val >= n:
    print(0)
else:
    another = n - max_val - 1
    for i in range(max_val+1):
        if another != 0:
            if i <= another - 1:
                if info.count(i) != 2:
                    print(0)
                    exit()
            else:
                if info.count(i) != 1:
                    print(0)
                    exit()
        else:
            if info.count(i) != 1:
                print(0)
                exit()
    if max_val+1 != another:
        print((2**another)*2)
    else:
        print(2**another)

해결방법

문제가 이해가 되지 않을 경우 입출력 예제를 보고 판단하는 것을 추천하는 문제.
경우의 수는 다음과 같다.

1. 경우의 수가 존재하기 위해서는 동물의 답변이 동물의 수를 넘지 않아야 함.
2. 경우의 수가 존재할 경우 두 동물의 수가 같은 경우가 다른 경우로 경우의 수가 나누어짐
3. 가장 큰 답변이 동물의 수를 넘지 않을 때 작은 동물의 수를 기준으로 그 값보다 미만인 경우에는 반드시 2개가 존재하며 이상인 경우에는 반드시 1개가 존재해야 함.

이렇게 언급한 조건들을 모두 구현하면 해결할 수 있는 문제.