[BOJ] 12907. 동물원 - JAVA 자바

 

12907번: 동물원

해당 문제는 동물들이 자신보다 키가 큰 고양이 or 토끼 수 를 말할 때, 각 대답이 어떤 동물이 했는지 가능한 경우의 수를 구하면 되는 문제이다.

 

이 문제의 핵심은 모든 동물의 키는 서로 다르다로 다음과 같은 특징을 알 수 있다.

1. 동물의 대답(입력값) 중 같은 값이 최대 2번 나올 수 있다.
예시) 자신보다 키가 큰 동물이 한 마리 있다고 토끼가 말한 경우와 고양이가 말한 경우로 최대 2번
2. 동물의 대답은 토끼 및 고양이 각각 연속된 수열로 이루어져 있다.
예시) 1 0 2 0 1 → { 2, 1, 0 } , { 1, 0 }

 

그래서 동물의 대답한 수를 counting 한 후, 가장 큰 값부터 0 까지 체크하면서 경우의 수를 세며 위의 특징을 어긴다면 바로 0을 출력해주면 된다.

 

경우의 수가 나올 수 없는 case ( 즉, 답이 0인 case )

#1. 동물의 수인 N보다 더 큰 값을 입력 받을 때
#2. 동물의 대답이 2번 보다 더 많이 입력 받을 때
#3. 가장 큰 값부터 0까지 체크할 때, 대답한 수 값이 2 가 나온 이후로 2 가 아닌 값이 나온 경우

연속된 수열이 2 개가 존재해야 하므로 arr[2] = 2 가 나온다면 2이하의 인덱스 값들은 무조건 2 가 나와야 한다. 즉, arr[1] = 2 , arr[0] = 2 가 되어야 함

#4. 대답한 수가 0인 경우 → 연속된 수열이 끊어지는 것을 의미

 

특수한 case

#4. 최대값이 0 이면서 동물의 수(N)이 2이하일 때, 각각 한 마리 씩 밖에 없는 경우로 답은 2
#5. 입력값이 모두 2 개씩 짝지어질 때, 같은 값끼리 자리만 바꾸면 되므로 답은 2^(N/2)

 

반례를 찾으면서 조건문을 계속 추가하며 해결할 수 있었다. 풀긴 풀었지만 그닥 잘 구현한 코드라고 생각은 안든다. 문제 의도는 비트마스킹을 사용하여 해결해야 하는 것 같다. 비트마스킹 공부 좀 더 하고 다시 풀어볼 예정 😂

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


/*
 * - 값이 2 인 경우는 고양이, 토끼 / 토끼, 고양이 가 될 수 있으므로 *2
 * 예 : 1 0 2 0 1     ( arr[1] = 2 이므로 * 2 )
 *     토 토 토 고 고
 *     고 토 토 고 토
 * - 반복문이 종료된 answer 값에 고양이 자리에 토끼, 토끼자리에 고양이 두는 경우까지 계산해서 *2
 * 예 : 1 0 2 0 1
 *     토 토 토 고 고
 *     고 고 고 토 토
 */

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        int max = 0;

        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            if (tmp >= N) { // #1
                System.out.println(0);
                return;
            }
            arr[tmp]++;
            if (arr[tmp] > 2) { // #2
                System.out.println(0);
                return;
            }
            max = Math.max(max, tmp);
        }

        int answer = 1;
        boolean flag = false;


        if (max == 0 && N <= 2) { // #4
            System.out.println(2);
            return;
        }

        int count = 0;


        for (int i = max; i >= 0; i--) {
            if (arr[i] == 2) {
                count++;
            }
        }
        if (count == max + 1) { // #5
            System.out.println((int) Math.pow(2, N / 2));
            return;
        }

        while (max >= 0) {
            if (arr[max] > 0) {
                if (flag && arr[max] < 2) { // #3
                    System.out.println(0);
                    return;
                } else if (arr[max] == 2) {
                    answer *= 2;
                    flag = true;
                }
            } else { // #4
                System.out.println(0);
                return;
            }
            max--;
        }

        System.out.println(answer * 2);

    }
}