백준 2407 조합 c++ [컴공과고씨]

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

2407번: 조합

 

문제 간단 정리

이 문제는 말 그대로 nCm을 구해주면 되는 문제이다.

nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다.

구하는 법은 n!/m!(n-m)! 이다.

 

문제 해결 방법 

이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다.

즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다. 

일단 써봐서 규칙을 찾아보는 것이다. 

      1C0 1C1

   2C0  2C1  2C2

  . . . . . . . . . .. . . .   이걸 구해 보면

  

                  1   1

                1   2   1

              1   3    3   1

            1   4   6    4    1

          1   5   10  10  5   1     이렇게 보면 규칙을 찾을 수 있다.

자신의 윗 줄 2개를 더하면 자신이 되는 걸 볼 수 있다. 

우리는 배열에 저장을 할 거기 때문에 배열에 쉽게 적용하기 위해서

1 1

1 2 1

1 3 3 1

1 4 6 4 1  이런식으로 만들어 주면 

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 로 구할 수 있다. 

 

즉,  다이나믹 프로그래밍을 이용하면 된다. (동적 계획법)

여기서 주의할 점은 문자열로 이 숫자들을 처리를 해주어야한다. 너무 큰 수 이기 때문에

 

일단 더 할 두 수를 string 으로 받아 준다.

그리고 한 자리씩 더하고 그것을 string 변수에 push해 줄 것이다.

이 부분 같은 경우 코드를 보면서 이해하는 게 편하다.

 

 

전체 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
 
    string dp[102][102];
    
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= i; j++){
            if(j == 0 || j == i)
                dp[i][j] = "1"; // m = 0 or n 이면 1
            else{
                int sum = 0; // 두 문자열의 한 자리를 더한 값
                string n1 = dp[i - 1][j]; // 더 할 문자열1
                string n2 = dp[i - 1][j - 1]; // 더 할 문자열2
 
                // 두 문자열 수를 더하기
                // 두 문자열을 모두 처리하고 남은 자릿수 sum까지 처리했으면 종료 
                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(); // 한 자리 제거 
                    }
                    // sum의 값 중 일의 자릿수 만 넣어주어함.
                    // 10의 나머지를 push해주고
                    dp[i][j].push_back((sum%10) + '0');
                    sum /= 10; // 10의 몫을 저장해주면 다음 자리수가 남음
                }
                // 위 방식대로 했다면 수가 일의 자리부터 시작됨.
                // 반대로 뒤집어주어서 답을 구해줌.
                reverse(dp[i][j].begin(), dp[i][j].end());
            }
        }
    }
    cout << dp[n][m];
    return 0;   
}