반응형

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

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 nCm의 값은 n-1Cm-1 + n-1Cm으로 표현할 수 있으므로 앞에서 구한 값을 더해서 자신의 값을 계산할 수 있습니다. 따라서 위와 같은 점화식을 사용해서 dp배열을 만들어 적용시켜 주었습니다. 

 

하지만 계산해야 할 수가 정수형으로 표현할 수 있는 값을 벗어나기에 숫자들을 string의 형태로 입력받고 string을 더해주는 함수를 따로 만든 후 각 숫자들을 더해주었습니다.

 

[ 소스 코드 ]

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <string>
 
using namespace std;
 
string dp[101][101];
 
string sum(string a, string b)                //a와 b를 더해주는 함수
{
    string ans = "";
 
    int lenA = a.size();
    int lenB = b.size();
    int len = max(lenA, lenB);
    int sum = 0;
    char num;
 
    while (lenB != len) {
        b = '0' + b;
        lenB++;
    }
    while (lenA != len) {
        a = '0' + a;
        lenA++;
    }
 
    for(int i=len - 1;i>=0;i--){
        sum = a[i] + b[i] - '0' - '0' + sum;
        num = sum % 10 + '0';
        ans = num + ans;
        sum /= 10;
    }
    if (sum != 0) {
        ans = (char)(sum + '0') + ans;
    }
 
 
    return ans;
}
 
string change(int num)                        //특정 int를 string의 형태로 바꿔주는 함수
{
    string ans = "";
    if (num > 99) {
        ans = "100";
    }
    else if(num > 9) {
        ans += (char)(num / 10 + '0');
        ans += (char)(num % 10 + '0');
    }
    else {
        ans = (char)(num + '0');
    }
 
    return ans;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= 100; i++) {
        dp[i][1] = change(i);
    }
    
 
    for (int i = 2; i <= 100; i++) {
        for (int j = 2; j <= i; j++) {
            if (i == j) {                    //n과 m이 같을 때는 1이므로
                dp[i][j] = "1";
            }
            else {                            //아닐 때는 nCm = n-1Cm-1 + n-1Cm을 대입
                dp[i][j] = sum(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    cout << dp[n][m];
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24

+ Recent posts

티스토리툴바