[USACO] Just Stalling JAVA

문제

www.acmicpc.net/problem/20975

20975번: Just Stalling

풀이 및 코드

import java.util.Scanner;

public class Main {

    // USACO Just Stalling JAVA
    // 백준 20975

    /**
     * 4
     * 1 2 3 4
     * 2 4 3 4
     * 예제의 경우
     * 키가 4인 소가 들어갈 수 있는 stall 의 갯수는 2개 (4,4)
     * 키가 3인 소가 들어갈 수 있는 stall 의 갯수는 2개 (4,3)           //4짜리 하나는 키가4인 소가 썼으므로
     * 키가 2인 소가 들어갈 수 있는 stall 의 갯수는 2개 (2, 3||4)       //키가 4인 소가 높이4짜리 한개, 키가 3인 소가 높이3또는4 짜리 한개 사용했으므로.
     * 키가 1인 소가 들어갈 수 있는 stall 의 갯수는 1개
     * <p>
     * 다시 생각해보니 이렇게 계산할 게 아니네.
     * <p>
     * 원래 모든 경우의 수를 생각해보면, 4x3x2x1 로 구할 수 있다.
     * (키가 큰 순서대로 정렬했다고 가정 4,3,2,1 하고)
     * 4 소는 높이가 2,3 인 것을 사용할 수 없고
     * 3 소는 높이가 2 인 것을 사용할 수 없고
     * 2 소는 모두 사용 가능
     * 1 소도 모두 사용 가능
     * 그러므로
     * 4 x 3 x 2 x 1 이 아니라
     * 2 x 2 x 2 x 1            //(4-2) x (3-1) x 2 x 1
     * 로 구하면 되겠다.
     */
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] cows = new int[n];
        int[] stalls = new int[n];
        long answer = 1;

        //cows
        for (int i = 0; i < n; i++) {
            cows[i] = sc.nextInt();
        }

        //stalls
        for (int i = 0; i < n; i++) {
            stalls[i] = sc.nextInt();
        }

        //둘 다 내림차순 (4,3,2,1) 정렬하기
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (cows[j] < cows[j + 1]) {
                    int temp = cows[j];
                    cows[j] = cows[j + 1];
                    cows[j + 1] = temp;
                }
                if (stalls[j] < stalls[j + 1]) {
                    int temp = stalls[j];
                    stalls[j] = stalls[j + 1];
                    stalls[j + 1] = temp;
                }
            }
        }

        //cows[i] 가 들어갈 수 없는 stall 의 갯수들을 구해서 minus 에 넣자
        int[] minus = new int[n];
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {//i번째 cow 랑 모든 stall 의 높이를 비교하며 못들어가는게 몇개인지 카운트
                if (cows[i] > stalls[j]) {
                    ++cnt;
                }
            }
            minus[i] = cnt;
        }

        //cows[i] 는 minus[i] 갯수만큼의 stall 은 못들어간다.
        //원래 식은 n ... 1 까지 곱하는거지만 n-x...1 까지 곱하면 된다.
        for (int i = n; i > 0; --i) {
            answer *= i - minus[n - i];   //minus[0] ,[1], [2] ... 이므로
        }

        System.out.println(answer);

    }//main

}//class