[백준/JAVA] 17213번: 과일 서리

📖 문제

17213번: 과일 서리

 

 

💡  풀이 방식

• DP

1. M*M 크기의 2차원 배열 dp를 만든다.

dp[ i ][ j ] : 과일 종류 j개 中 i개를 훔치는 경우의 수

 

 

2. dp배열의 초기값을 채운다.

• 과일 i종 중 중 i개 훔치는 경우의 수 : 1
• 과일 1종 중 중 i개 훔치는 경우의 수 : 1

3. 나머지 원소들은 점화식을 통해 채운다.

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());    // 과일 종류
        M = Integer.parseInt(br.readLine());    // 훔치려 하는 과일 갯수
        
        dp = new int[M + 1][M + 1]; // dp[i][j] : 과일 j종 中 i개 뽑는 경우의 수
        
        for(int i = 1 ; i <= M ; i++) {
            dp[i][i] = 1;   // 과일 i종 中 i개 뽑는 경우의 수 : 1
            dp[i][1] = 1;   // 과일 1종 中 i개 뽑는 경우의 수 : 1
        }
        
        for(int i = 1 ; i <= M ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                if(i == j)  continue;
                
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        
        System.out.println(dp[M][N]);
    }
}
 

 

 

➕ 다른 풀이 방식

N가지 종류 중 (M-N)개 뽑는 중복 조합을 활용해 푸셨다.

[백준/17213번/C++, Java] 과일 서리

https://www.acmicpc.net/source/13377364

import java.util.Scanner;

public class Main {
    public static int comb(int n, int r) {
        if(n == r || r == 0) 
            return 1; 
        return comb(n - 1, r - 1) + comb(n - 1, r);	// 현재 요소를 선택하는 경우 + 선택하지 않는 경우
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        System.out.println(comb(m-1, m-n));
    }
}

 

 

---

💦 어려웠던 점

30분 소요

- 초반에 미리 N개 뽑아뒀다고 생각하고  N가지 종류 中 (M-N)개 뽑는 식으로 풀까라는 생각을 했었다...⇒ 중복 조합이었음

- 나는 직접 그려보면서 점화식 세웠었는데 채우는 과정 그림은 이 글을 참조하도록 하자.. (링크)

 

 

1회독	2회독	3회독	4회독	5회독
V

 

 

 

(참고)

중복 조합

: 주어진 n개의 요소 중에서 중복을 허용하여 m개를 선택하는 경우의 수를 계산

중복조합 공식