문제 출처: https://www.acmicpc.net/problem/11051
풀이
nCr == n-1Cr + n-1Cr-1로 표현할 수 있고 아래 내용들만 알고있으면 쉽게 dp 2차원배열로 풀수 있습니다.
1. r이 1이면 n에 상관없이 무조건 n
2. n==r이면 무조건 1
3. r이 0이면 무조건 1
2중for문에서 i가 3, j=2부터 시작되는 이유는
i가 3보다 작을 때는 위의 3가지 조건들을 미리 계산해놓으면 아래 식 까지 계산되어서 굳이 또 계산할 필요가 없기 때문입니다.
1 1
2 1
2 2
3 1
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include<iostream> using namespace std; int dp[1001][1001]; int main() { //nCr==n-1Cr + n-1Cr-1 int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { dp[i][1] = i; dp[i][i] = 1; dp[i][0] = 1; } for (int i = 3; i <= n; i++) { for (int j = 2; j < i; j++) { dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007; } } cout << dp[n][k] % 10007 << endl; } | cs |
결과
'문제풀이(BOJ) > 수학' 카테고리의 다른 글
[백준 17206] 준석이의 수학 숙제 (0) | 2020.03.11 |
---|---|
[백준 13301] 타일 장식물 (0) | 2020.03.11 |
[백준 1339] 단어 수학 (0) | 2020.02.09 |
[백준 11444] 피보나치 수6 (0) | 2020.01.19 |
[백준 1448] 삼각형 만들기 (0) | 2020.01.13 |