[백준/JAVA] 13251번: 조약돌 꺼내기

🔺 문제

13251번: 조약돌 꺼내기

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int M, K, T;
    static int[] D = new int[51];                   // 색깔별 조약돌 개수
    static double probability[] = new double[51];   // 색깔별 확률
    static double ans;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        M = Integer.parseInt(br.readLine());    // M : 색 종류
        
        // 색깔 별 조약돌 개수 저장
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0 ; i < M ; i++) {
            D[i] = Integer.parseInt(st.nextToken());
            T += D[i];  // 조약돌 개수 더하기
        }
 
        // 한 색깔 조약돌만 뽑을 확률을 색깔별로 모두 계산
        K = Integer.parseInt(br.readLine());    // K : 선택 조약돌 개수
        ans = 0.0;
        
        for(int i = 0 ; i < M ; i++) {
            if(D[i] >= K) {
                probability[i] = 1.0;
                
                for(int k = 0 ; k < K ; k++) {
                    probability[i] *= (double) (D[i] - k) / (T - k);
                }
            }
            ans += probability[i];  // 각각의 확률 더하기
        }
        System.out.println(ans);
        br.close();
    }
}

✅ 해결 아이디어
✔ 조합. DP. 점화식
- 27~ 36번째 줄! (특히 31~32번째줄! )

 

 

---

🔺 다른 풀이들

- 과정 설명 굿!! (복습용)

백준 13251 조약돌 꺼내기

 

 

- 확률 값 저장해두는 배열 따로 안 하고 ratio라는 변수 하나로 결과까지 도출하심 굿!

 

BOJ) 조약돌 꺼내기

---

💬 느낀 점

역시 수학을 못 하니... 이런 점화식 간단하게 세우는 것도 머리를 써야한다,,

분발하자!!

 

 

 

 

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

 

 

(+7/3 2회독)

점화식이 보인다.. 한 번 풀어봤던 문제라 그런것인지..?!

암튼 저번 코드랑 거의 비슷하다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int M, pick, total;
    static int[] arr = new int[51];           // 색깔별 조약돌 개수
    static double[] prob = new double[51];    // 색깔별 확률
    static double ans = 0.0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        M = Integer.parseInt(br.readLine());    // 총 조약돌 수
        arr = new int[51];
        prob = new double[51];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < M ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());  // 색깔 별 조약돌 개수 저장
            total += arr[i];                            // 총 조약돌 개수 저장
        }
        int pick = Integer.parseInt(br.readLine());    // 뽑은 조약돌 수
        
        // 조약돌이 모두 같은 색일 확률
        for(int i = 0 ; i < M ; i++) {
            if(arr[i] >= pick) {    // 🔔 해당 색의 조약돌 개수가 뽑는 개수보다 많을 경우! 🔔
                prob[i] = 1.0;
                
                for(int j = 0 ; j < pick ; j++) {
                    prob[i] *= (double) (arr[i] - j) / (total - j);
                }              
            }
            ans += prob[i];    // 각 확률 더하기
        }
        
        System.out.println(ans);
    }
}
 

 

---

(참고)

✔ DO it 알고리즘 코딩테스트 자바편