프로.입문.구슬을 나누는 경우의 수, 조합

• 서로 다른 n개 중 m개를 뽑는 경우의 수

       n! 

---------------

(n-m)! * m!

 

팩토리얼을 사용할 경우 factorial(20)만 되어도 long long 범위를 넘게된다.

 

-> 경우의 수, 순열 조합을 공부해와서 다시 풀었다.

 

이 경우, 값이 커지면 음수가 된다. 

위의 상황과 마찬가지이다. 이것도 팩토리얼을 for문으로 이용한거니까.

int solution(int balls, int share) {
    int answer = 1;
    int rFactorial = 1;

    //r!
    for (int i = 1; i <= share; ++i)
    {
        rFactorial *= i;
    }

    //nPr
    while (share--)
    {
        answer *= balls--;
    }

    answer /= rFactorial;



    cout << answer << endl;
    return answer; 
}

 

그래서 nCn-r == nCr 를 적용시켜주었음에도 fail이었다. 이번엔 74점.

//nCr
int solution(int balls, int share) {
    int answer = 1;
    int rFactorial = 1;

    //nCn-r == nCr
    if (balls - share < share)
    {
        share = balls - share;
    }

    //r!
    for (int i = 1; i <= share; ++i)
    {
        rFactorial *= i;
    }

    //nPr
    while (share--)
    {
        answer *= balls--;
    }

    answer /= rFactorial;

    return answer; 
}

 

double로 바꾸고 마지막에 int 형변환해서 풀었다. 6점짜리 문제였다니..

나도 경우의 수 안배우고 왔으면 못풀었을 것이다.

 

이제 더 효율적인 코드를 알아보자.

 

 

문제점 분석

1. double 형 사용: 부동 소수점 연산은 정확하지 않을 수 있습니다. 특히, 큰 수의 팩토리얼 계산 과정에서 오차가 누적될 수 있으며, 최종 결과를 int 형으로 변환하는 과정에서 오차가 더 커질 수 있습니다.
2. 불필요한 계산: nPr 계산 과정에서 balls를 1씩 감소시키면서 곱셈을 수행하는데, 이는 비효율적인 방법입니다.

개선된 코드

C++

 

#include <iostream>

using namespace std;

int solution(int balls, int share) {
    if (share < 0 || share > balls) {
        return 0; // 예외 처리: 잘못된 입력
    }

    if (share == 0 || share == balls) {
        return 1; // 예외 처리: nC0 = nCn = 1
    }

    if (share > balls / 2) {
        share = balls - share; // nCr == nC(n-r)
    }

    long long result = 1;
    for (int i = 1; i <= share; ++i) {
        result = result * (balls - i + 1) / i; // 핵심: 곱셈 후 나눗셈
    }

    return (int)result;
}

int main() {
    cout << solution(30, 16) << endl; // 출력: 145422675
    return 0;
}

주요 변경 사항

1. long long 형 사용: 계산 결과를 long long 형으로 저장하여 오버플로우 가능성을 줄였습니다.
2. 곱셈 후 나눗셈: 분수 형태의 계산에서 곱셈을 모두 수행한 후 나눗셈을 하는 대신, 곱셈과 나눗셈을 번갈아 수행하여 중간 결과 값이 커지는 것을 방지했습니다.
3. 예외 처리: 입력 값이 유효하지 않은 경우에 대한 예외 처리를 추가했습니다.
4. nCr == nC(n-r) 활용: share가 balls / 2보다 크면 balls - share로 값을 변경하여 계산 횟수를 줄였습니다.

추가적인 최적화 방법

• 룩업 테이블 활용: balls와 share의 값이 작으므로, 미리 계산된 조합 값을 2차원 배열 형태의 룩업 테이블에 저장해두면 더욱 빠르게 결과를 얻을 수 있습니다.
• 동적 프로그래밍: 파스칼의 삼각형을 이용하여 조합 값을 계산하는 동적 프로그래밍 방식을 적용할 수 있습니다.