[Baekjoon] 13251 - 조약돌 꺼내기

📝 문제

 

 

🔑 풀이 과정

처음엔 조합 문제길래, 당연하게 DP배열을 사용해서 풀이했다.

DP배열 사용했을때 코드

분명 예제 4개도 잘 맞았는데, 막상 제출하니 2퍼에서 "틀렸습니다" 받은 ^^...

(근데 아직도 왜 틀린지를 모른다 ㅠ 차라리 메모리 초과, 시간 초과면 고쳐보겠는데...)

 

그래서 다른 풀이법을 사용했다.

말보다 그림이 편할 것 같아서 그림 첨부

확률 풀이

조합식(nCr = n! / r! * (n-r)!) 을 사용하는게 아닌, 그냥 일반적인 확률을 구하는 과정을 손으로 풀어봤다.

 

그랬더니 일정한 패턴?이 반복되는 것 처럼 보였다.

분모는 조약돌의 총합(N)부터 1씩 감소하면서 총 K번(뽑는 조약돌의 수)이 나오고,

분자는 각 색깔별 조약돌의 수 부터 1씩 감소하는게 총 K번이 나온다.

 

그리고 이 과정이 총 M번(조약돌의 색의 수)만큼 반복된다.

이를 이중 for문으로 계산했다.

 

* 특정 알고리즘을 정답이라고 생각하는 좁은 시야를 버릴 것. 조합이라고 무조건 DP배열이 답이 아니라는 것...

 

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //첫번째 줄 입력 받기
        int M = Integer.parseInt(br.readLine());
        int[] arr = new int[M];
        //두번째 줄 입력 받기, 조약돌의 총 갯수(N) 구하기
        st = new StringTokenizer(br.readLine());
        int N = 0;
        for(int i = 0; i < M; i++){
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
            N += num;
        }
        //세번째 줄 입력받기
        int K = Integer.parseInt(br.readLine());
        //-- 입력 끝

        double answer = 0.0;
        for(int i = 0; i < M; i++){
            double probability = 1.0;

            int numerator = arr[i];
            int denominator = N;
            for(int j = 0; j < K; j++){
                probability *= (double)numerator / denominator;

                numerator--;
                denominator--;
            }
            answer += probability;
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 수학

- 조합론

- 확률론