BOJ
BOJ::2407 조합
BOJ Silver 2
BOJ::2407 조합
- Link : BOJ::2407
- Level : Silver 2
- tag : combination
시사점
- 조합 nCk에 대한 값을 구합니다.
- n이 일정 수준보다 큰 해당 문제 같은 경우, 일반 dp + string으로 해결해주어야 합니다.
이해(x)
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
시간 복잡도
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(x)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<bits/stdc++.h>
#define endl '\n'
#define se second
#define fi first
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef unsigned long long ll;
string dp[100+2][100+2];
string add(string a, string b){
string s = "";
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
if(a.size() > b.size()) swap(a, b);
int carry = 0;
int diff = (int)(b.size() - a.size());
rep(i, 0, diff) a+='0';
rep(i, 0, a.size()){
int sum = (a[i]-'0') + (b[i]-'0') + carry;
carry = sum/10;
s += sum%10+'0';
}
if(carry) s += carry+'0';
reverse(s.begin(), s.end());
return s;
}
void process(){
int n, k;
cin >> n >> k;
dp[1][1] = "1";
rep(i, 2, n+2){
rep(j, 1, i+1){
dp[i][j] = add(dp[i-1][j-1], dp[i-1][j]);
}
}
cout << dp[n+1][k+1] << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.