×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,238,771명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. 파스칼 삼각형


아래 그림의 원리를 이용한다면 빠르게 DP를 구할 수 있다.


0C0부터 시작해서 nCk까지 Dynamic Programming을 통해 구할 수 있게 된다.


combi[1001][1001]배열의 의미는 combi[n][k] 즉, nCk의 의미를 가지도록 배열을 구성한 것이다.




nCr = n-1Cr-1 + n-1Cr



소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <memory.h>
 
using namespace std;
 
int combi[1001][1001];
int main()
{
    int n, k;
 
 
    cin >> n >> k;
 
    combi[0][0= 1;
    combi[1][0= 1;
    combi[1][1= 1;
 
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            combi[i][j] = combi[i - 1][j - 1] % 10007 + combi[i - 1][j] % 10007;
            combi[i][j] %= 10007;
        }
    }
 
    cout << combi[n][k];
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



combination dp 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
#define MAX 101
#define MIN(a,b) (a < b ? a : b)
 
int comb[MAX][MAX];
 
void makeComb(int n, int r) {
    comb[0][0= 1;
    for (int i = 1; i <= n; i++) {
        int len = MIN(i, r);
        for (int j = 0; j <= len; j++// 5C2는 있지만 2C5는 없다.
            comb[i][j] = comb[i - 1][j - 1+ comb[i - 1][j];
    }
}
 
int main() {
    int n = 10, r = 10;
    makeComb(n, r);
    for (int i = 0; i <= 10; i++) {
        for (int j = 0; j <= 10; j++) {
            printf("%4d", comb[i][j]);
        }
        printf("\n");
    }
}
cs


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1786번] 찾기 (KMP Algorithm)  (0) 2016.11.02
[10448번] 유레카 이론  (0) 2016.11.02
[11051번] 이항 계수 2  (2) 2016.11.02
[1193번] 분수찾기  (0) 2016.11.02
[1111번] IQ Test  (2) 2016.11.02
[13419번] 탕수육  (0) 2016.10.31
  1. kimsy96 2018.01.23 16:05

    오늘도 왔습니다 하하..
    다름이 아니라 최근에 이항계수 유형을 공부하면서 파스칼의 삼각형을 알게 되었고 이문제를 파스칼의 삼각형,dp를 응용해서 풀었습니다. 그런데 틀렸다고 뜨더라고요
    아무리 봐도 틀린곳이없었고(파스칼만 안다면 dp중에서도 가장 쉬운 유형이니..) 질문검색을 봐도 제가 틀린곳이없어서 다른 고수분들 풀이를 찾아봤는데 풀이가 거의 같더라고요
    혹시나 해서 크로커스님 풀이를 그냥 복붙해서(데이터의 문제인가해서요.. 복사 죄송합니다) 제출해봤는데
    틀렸다고 뜨네요. 혹시 알고계셨나요?

  2. kimsy96 2018.01.23 16:13

    채점서버의 문제라고하는군요