[백준][C++] 2407 조합

2407 조합

2407번: 조합

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

조합을 쓰는 문제! 다리 놓기랑 비슷한 문제라고 생각했지만...

(5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

많이 커진 입력값이 문제였다.

nCm = nC(n-m)

이 공식도 고려해봤을 때... 가장 큰 출력을 일으키는 입력은 n=100, m=50이다. 이걸 조합으로 계산해봤을 땐...

unsigned long long int
=> 18446744073709551615

100C50
=> 100891344545564193334812497256

망했다고 볼 수 있었다. 하하.

다리 놓기같은 방식은 쓰지 못한다는 것...

 

설마 해서 분수를 나누고 어떻게 해서 몇 번을 코드를 써서 제출해봤지만 결과는 실패...

 

c++에 더 큰 자료형을 찾아보다가, 백준의 채점 컴파일러 gcc에서는 __uint128_t라는 128비트의 정수 자료형을 제공해준다는 이야기를 들었다.

 

비주얼 스튜디오에서 실행해봤더니... 오류가 떴다.

비주얼 스튜디오는 gcc 컴파일러를 지원하지 않는 건가?

 

난 그래서 웹 컴파일러로 찾아서 돌렸고, 애석하게도 저 자료형은 바로 출력이 지원되지 않는다는 것을 알았다.

그리 치명적인 문제는 아니었다. 배열에 뒤에서부터 각 자리의 숫자를 int형으로 담아준 다음에, 리버스를 해서 출력했다.

 

알고리즘 설계

1. m이 n-m보다 크면 m에 n-m을 대입한다.
2.  
3. 5C3 = 5C2
4. 분모는 오름차순, 분자는 내림차순으로 곱해준다.

5 x 4    5    4
----- = --- x ---
2 x 1    1     2

= 10

1. 128바이트의 자료형이 0이 될 때까지 10으로 나눈 값을 벡터에 넣고, 10으로 나눈다.
2. 벡터를 역순 출력한다!

 

코드

#include<bits/stdc++.h>
using namespace std;

int main()
{
    __uint128_t answer = 1;
    vector<int> v;
    int n, m;
    cin >> n >> m;

    // nCm = nC(m-n)
    if (m > n - m)
        m = n - m;

    // 조합 계산
    for (int i = 0; i < m; i++)
    {
        answer *= (n - i);
        answer /= (i + 1);
    }

    // 벡터에 역순으로 넣기
    while (answer)
    {
        v.push_back(answer % 10);
        answer /= 10;
    }

    // 리버스
    reverse(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i];
    }
}

어려웠던 문제...

__uint128_t이 있다니 너무 신기했다! 2^128이면 얼마나 큰 걸까... 기억해놔야겠다...