11051 : 이항계수2 (Binomial Coefficient) (Dynamic Programming) [C++]

저번 이항 계수의 문제와 비슷하지만

입력 값의 범위가 1000까지 늘어서 DP를 이용하기에 딱 좋은 문제이다.

왜 DP를 이용하는가?

이항계수의 원리를 보면 파스칼의 삼각형 형태!

1(1C0) 1(1C1)

1(2C0) 2(2C1) 1(2C2)

1(3C0) 3(3C1) 3(3C2) 1(3C3)

1(4C0) 4(4C1) 6(4C2) 4(4C3) 1(4C4)

1(5C0) 5(5C1) 10(5C2) 10(5C3) 5(5C4) 1(5C5)

1(6C0) 6(6C1) 15(6C2) 20(6C3) 15(6C4) 6(6C5) 1(6C6)

<파스칼의 삼각형(이항원리)>

DP식을 써보면

///////////////////////////////////////////////////////////

if (k == 0 || k == n)

DP[i][j] = 1;

else

DP[i][j] = DP[i-1][j-1] + DP[i-1][j];
///////////////////////////////////////////////////////////

BinomialCoefficient::BinomialCoefficient(int N)
{
    for(int i = 0; i < N; i++)
    {
        vector<int> Temp;
        Temp.resize(i+2);
        DP.push_back(Temp);
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < i + 2; j++)
        {
            if(j == 0 || j == i + 1)
                DP[i][j] = 1;
            else
                DP[i][j] = DP[i-1][j-1] % 10007 + DP[i-1][j] % 10007;
        }
    }
}

void BinomialCoefficient::Print(int N, int K)
{
    cout << DP[N-1][K] % 10007;
}

<소스 코드>

*Source of the problem = https://www.acmicpc.net/problem/11051

*문제 출처 : BAEKJOON ONLINE JUDGE

이 블로그의 인기 게시물

1094 : 막대기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { vector < int > Stick ; Stick . push_back ( 64 ) ; int Target ; cin > > Target ; int Last = 0 ; while ( true ) { if ( Target = = 64 ) break ; int Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target = = Sum ) break ; else if ( Target < Sum ) { Stick [ Last ] / = 2 ; Sum = 0 ; for ( int i = 0 ; i < Stick . size ( ) ; i + + ) Sum + = Stick [ i ] ; if ( Target < = Sum ) continue ; else Stick . push_back ( Stick [ Last + + ] ) ; } } cout < < Stick . size ( ) ; ...

자세한 내용 보기

2407 : 조합 (Dynamic Programming) [C++]

어려웠다. 문제를 풀면서 솔직히 이게 되려나?? 메모리 제한걸리려는게 아닌가 싶었는데 만들면서 최대한 메모리를 작게 만들었더니 맞았습니다! 주어진 입력 값은 최대 100인데, 입력값을 입력하면 오버플로우가 나므로 자릿수 배열을 만들어주어야 한다! 처음으로 한 생각은 재귀! (n == m || m == 0) 참이면 1 거짓이면 [n-1], [n]번째에 계속 접근하기 결과는 20이 넘어가면 엄청난 시간이 걸림. 두 번째 한 생각은 3차원 배열이었다. 2차원 배열에 또 배열을 만들어 자릿 수를 다 저장하려 했으나~ for문이 3개나 들어가서 시간이 엄청 오래걸렸음. 결국 2차원 배열이지만 3차원의 효과를 내게끔 선언하였다. 2차원배열이 원래이런 식이라면 1 11 121 1331 14641 내가 만든 배열은 111121133114641 즉 한 차원을 줄일 수 있었고, 각 원소에 대한 파스칼의 삼각형을 이용한 덧셈 공식은 그 줄의 자릿수 사이즈를 이용하여 전에 있는 줄에 접근하였다. DP 사용!! Answer[i] = Answer[i-Answer[i].size()] + Answer[i-Answer[i].size()+1] 그리고 저장한 자릿수들을 거꾸로 출력해주면 그것이 정답! Combination() : 각 줄의 번호만큼 자릿수를 가지는 벡터 생성, 계속 쓰는 Sum 벡터 생성 Increase() : 각 자릿수가 10이 넘어가면 올림을 해준다. GetSum() : 각 자릿수를 더해준다. GetAnswer() : DP, 올림, 출력 Combination :: Combination ( ) { this - > Sum . push_back ( 0 ) ; for ( int i = 1 ; i < = 101 ; i + + ) Sum . push_back ( S...

자세한 내용 보기

11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...

자세한 내용 보기

MrCodeMania

이 블로그 검색