백준 (BOJ) 17213 과일 서리 java dp

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

17213번: 과일 서리

 

중복 조합과 dp의 콜라보

 

N개의 자리를,

 

N개를 뺀 M개(과일이 최소 하나씩 필요하므로)에 할당하는 문제.

 

(n) H (m-n) = (n+(m-n)-1) C (m-n) = (m-1) C (m-n) = (m-1) C (n-1)

 

연산량을 줄이기 위해 계산 시작 전에 판별식을 넣었다.

 

채점 속도 차이는 없는 듯 하다.

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        long up = 1;
        long down = 1;

        int mMinus1 = M-1;
        int nMinus1 = N-1;

        if(nMinus1 < mMinus1){
            int count = nMinus1;
            int i = mMinus1;
            while (count != 0){
                up *= i;
                --i;
                --count;
            }

            for(i=1; i<=nMinus1; i++) {
                down*= i;
            }
        }
        else{
            int count = M-N;
            int i = mMinus1;
            while (count != 0){
                up *= i;
                --i;
                --count;
            }

            for(i=1; i<=M-N; i++) {
                down*= i;
            }
        }

        System.out.print(up/down);

    }
}

 

 

 

처음에 독특하게 접근해서 풀이한 방식

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        if(N == 1){
            System.out.print(1);
            return;
        }
        int rowNum = M - N + 1;
        int nOfCombination = N - 1;
        long[] dp = new long[rowNum];
        dp[0] = 1;
        for(int rOfCombination=1; rOfCombination<rowNum; ++rOfCombination){
            // bigger num check
            int nMinus1 = nOfCombination - 1;
            long combRst;

            // n-1+r C r == n-1+r C n-1
            if(nMinus1 < rOfCombination){
                combRst = combination(nMinus1 + rOfCombination, nMinus1);
            }
            else{
                combRst = combination(nMinus1 + rOfCombination, rOfCombination);
            }

            dp[rOfCombination] = dp[rOfCombination-1] + combRst;
        }

        System.out.print(dp[rowNum-1]);
    }

    static long factorial(int num){
        long rst = 1;
        for(; 0<num; --num){
            rst *= num;
        }
        return rst;
    }

    static long combination(int n, int r){
        long rst = 1;

        // i == 반복 횟수
        int i = r;
        while (i != 0){
            rst *= n;
            --n;
            --i;
        }

        return rst / factorial(r);
    }
}