[백준] 12907 동물원

www.acmicpc.net/problem/12907

12907번: 동물원

 

N = int(input())
ans_list = list(map(int, input().split()))
ans_dict = dict(zip(range(41),[0] * 41))

for i in range(N):
    index = ans_list[i]
    ans_dict[index] += 1
    
len1 = 0
for i in range(41):
    if ans_dict[i] == 0:
        len1 = i
        break
    else:
        ans_dict[i] -= 1

len2 = 0
for i in range(41):
    if ans_dict[i] == 0:
        len2 = i
        break
    else:
        ans_dict[i] -= 1
        
break_chk = False
for i in range(41):
    if ans_dict[i]:
        break_chk = True
        break

if break_chk:
    print(0)
elif len1 == len2:
    print(1 << (len2))
else:
    print(1 << (len2 + 1))

 

그리디로 풀어서 그런지 푸는데 오래걸렸다.

조합이어서 백트래킹으로 구할까 생각했는데 그냥 조합을 하지않아도 충분히 구할수 있다고 생각했다.

 조합하라고 주어진 리스트는 0부터 스트레이트로 올라가야한다.

예를 들면 두 마리의 동물이 있을때, 본인보다 큰 동물이 0마리, 2마리 있다고 하면 조합이 불가능하고

세마리 동물이 있을때, 본인보다 큰 동물이 0,1,2 마리 씩 있으면 조합이 가능하다.

동물이 토끼랑 고양이 밖에 없으므로 스트레이트로 올라가는 것을 두 번 세면된다.

이때 최대로 올라갈수 있는 길이를 체크하고 두개중 작은 길이까지 조합할수 있다.

 

어찌되었든 그렇게 뚱땅뚱땅 조합을 하고 나면 2의 제곱수로 표현이 되므로 답을 구할수 있었다.