2407번: 조합

문제 링크

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

2407번: 조합

 

문제 풀이 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;
const int MN = 101;
string dp[MN][MN];

string sumString(string a, string b){
    long long sum = 0;
    string ret;
    while(a.size()||b.size()||sum){
        if(a.size()){
            sum+=a.back()-'0';//숫자로 변환
            a.pop_back();
        }
        if(b.size()){
            sum+=b.back()-'0';//숫자로 변환
            b.pop_back();
        }
        ret.push_back((sum%10)+'0');//문자로 변환
        sum/=10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

int main(void){
    ios::sync_with_stdio(false); cin.tie(NULL);
    
    long long N, M; cin>>N>>M;
    
    for(int i=1; i<=N; i++){
        for(int j=0; j<=i; j++){
            if(j==0||i==j) dp[i][j]="1";
            else dp[i][j] = sumString(dp[i-1][j-1],dp[i-1][j]);
        }
    }

    cout<<dp[N][M];

    return 0;
}

자신있게 long long int형 DP방식으로 풀었다가 자꾸 틀려서

정수형이 아닌 string 형으로 문제를 해결해야함을 깨달았다.