백준 2407 c++(파스칼 삼각형) / python(factorial)

https://www.acmicpc.net/problem/2407

2407번: 조합

 

 

맨 처음에는 생각을 하지 않고, 그냥 queue에 값을 넣고, 큰 수가 나오면 에라토스테네스의 체를 통해 곱하는 값에 대해서 조정하면 되지 않을까?라는 생각으로 접근했다. 

 

이렇게 생각없이 접근하면 헛고생만 합니다.. 꼭 문제 풀기 전에 범위 벗어나는지 확인해야 합니다...

 

문제에서 나올 수 있는 값에 최댓값에 전혀 미치지 못하는 long long int의 범위이다..

 

그러면 어떻게 풀면 될까? 

이런 문제는 거의 다 문자열로 풀이가 가능하다.

 

 

아래는 22%에서 터지는 코드인데 왜 터질까?

#include <iostream>
#include <string>
#include <algorithm> // reverse 함수

using namespace std;

int n, m;
string factorial[101][101];

string bigNumAdd(string n1, string n2)
{
    int sum = 0;
    string result;

    // 1의 자리부터 더하기
    while (!n1.empty() || !n2.empty() || sum)
    {
        if (!n1.empty())
        {
            sum += n1.back() - '0';
            n1.pop_back();
        }
        if (!n2.empty())
        {
            sum += n2.back() - '0';
            n2.pop_back();
        }
        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
                                   
    // 1의 자리부터 push 했으므로 뒤집어준다.
    reverse(result.begin(), result.end());
    return result;
}

string combination(int n, int r)
{
    if (n == r || r == 0)
        return "1";
    string& result = factorial[n][r]; // 참조형 변수

    // 이미 계산했으면 바로 return, memoization 기법
    if (result != "")
        return result;

    // 파스칼삼각형 원리 이용
    result = bigNumAdd(combination(n - 1, r - 1), combination(n - 1, r));
    return result;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    //미리 값을 넣어주기 
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            if (j == 0 || i == j) {
                factorial[i][j] = "1";
            }
            else if (j == 1) {
                factorial[i][j] = i + '0';
            }
        }
    }
    cout << combination(n, m);

    return 0;
}

 

main문에 2중 반복문으로 조합에 대한 값에 대해서 미리 연산을 해서 대입을 하는 식의 형태로 값을 저장해 놨는데, 이게 10이 넘어가는 순간부터 값이 이상해진다. 

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < 101; i++) {
        for (int j = 0; j < 101; j++) {
            if (j == 0 || i == j) {
                factorial[i][j] = "1";
            }
            else if (j == 1) {
                factorial[i][j] = i + '0';
            }
        }
    }
    cout << combination(n, m);

    return 0;
}

 

그렇기에 이중반복문을 지우고, 다시 코드를 돌려봤다.

#include <iostream>
#include <string>
#include <algorithm> // reverse 함수

using namespace std;

int n, m;
string factorial[101][101];

string bigNumAdd(string n1, string n2)
{
    int sum = 0;
    string result;

    // 1의 자리부터 더하기
    while (!n1.empty() || !n2.empty() || sum)
    {
        if (!n1.empty())
        {
            sum += n1.back() - '0';
            n1.pop_back();
        }
        if (!n2.empty())
        {
            sum += n2.back() - '0';
            n2.pop_back();
        }
        result.push_back((sum % 10) + '0');
        sum /= 10;
    }
                                   
    // 1의 자리부터 push 했으므로 뒤집어준다.
    reverse(result.begin(), result.end());
    return result;
}

string combination(int n, int r)
{
    if (n == r || r == 0)
        return "1";
    string& result = factorial[n][r]; // 참조형 변수

    // 이미 계산했으면 바로 return, memoization 기법
    if (result != "")
        return result;

    // 파스칼삼각형 원리 이용
    result = bigNumAdd(combination(n - 1, r - 1), combination(n - 1, r));
    return result;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    cout << combination(n, m);

    return 0;
}

 

정답 코드

 

번외 python 

import math

n, m = map(int, input().split())
up = math.factorial(n)
down = (math.factorial(n - m)) * (math.factorial(m))
print(up // down)

 

너무하다는 생각 밖에.. 문자열이랑, 큰 수 구하는 코드는 앞으로 파이썬으로 해야겠다...