https://www.acmicpc.net/problem/2407
문제 간단 정리
이 문제는 말 그대로 nCm을 구해주면 되는 문제이다.
nCm 이란 서로 다른 n개 중 m개를 뽑는 방법을 말한다.
구하는 법은 n!/m!(n-m)! 이다.
문제 해결 방법
이런 문제 같은 경우 공식을 구현하기 할 수는 있겠지만 답이 겁나게 크게 나오는 걸 볼 수 있다.
즉, c++에서는 저런 큰 수를 정수로 담을 변수가 없기도 하고 공식 구현 하더라도 일일이 다 곱하는 팩토리얼이 있기 때문에 시간초과가 걸릴 수 밖에 없다.
일단 써봐서 규칙을 찾아보는 것이다.
1C0 1C1
2C0 2C1 2C2
. . . . . . . . . .. . . . 이걸 구해 보면
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1 이렇게 보면 규칙을 찾을 수 있다.
자신의 윗 줄 2개를 더하면 자신이 되는 걸 볼 수 있다.
우리는 배열에 저장을 할 거기 때문에 배열에 쉽게 적용하기 위해서
1 1
1 2 1
1 3 3 1
1 4 6 4 1 이런식으로 만들어 주면
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] 로 구할 수 있다.
즉, 다이나믹 프로그래밍을 이용하면 된다. (동적 계획법)
여기서 주의할 점은 문자열로 이 숫자들을 처리를 해주어야한다. 너무 큰 수 이기 때문에
일단 더 할 두 수를 string 으로 받아 준다.
그리고 한 자리씩 더하고 그것을 string 변수에 push해 줄 것이다.
이 부분 같은 경우 코드를 보면서 이해하는 게 편하다.
전체 코드
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
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
string dp[102][102];
for (int i = 1; i <= n; i++){
for (int j = 0; j <= i; j++){
if(j == 0 || j == i)
dp[i][j] = "1"; // m = 0 or n 이면 1
else{
int sum = 0; // 두 문자열의 한 자리를 더한 값
string n1 = dp[i - 1][j]; // 더 할 문자열1
string n2 = dp[i - 1][j - 1]; // 더 할 문자열2
// 두 문자열 수를 더하기
// 두 문자열을 모두 처리하고 남은 자릿수 sum까지 처리했으면 종료
while(!n1.empty() || !n2.empty() || sum){
if(!n1.empty()){ // 비어있으면 처리할 필요없음.
sum += n1.back() - '0'; // 한 자리 더해줌
n1.pop_back(); // 한 자리 제거
}
if(!n2.empty()){ // 비어있으면 처리할 필요없음.
sum += n2.back() - '0'; // 한 자리 더해줌
n2.pop_back(); // 한 자리 제거
}
// sum의 값 중 일의 자릿수 만 넣어주어함.
// 10의 나머지를 push해주고
dp[i][j].push_back((sum%10) + '0');
sum /= 10; // 10의 몫을 저장해주면 다음 자리수가 남음
}
// 위 방식대로 했다면 수가 일의 자리부터 시작됨.
// 반대로 뒤집어주어서 답을 구해줌.
reverse(dp[i][j].begin(), dp[i][j].end());
}
}
}
cout << dp[n][m];
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
백준 1238 파티 c++ [컴공과고씨] (0) | 2023.01.02 |
---|---|
백준 1043 거짓말 c++ [컴공과고씨] (3) | 2022.11.20 |
백준 1692 곱셈 c++ [컴공과고씨] (2) | 2022.11.10 |
백준 1932 정수 삼각형 c++ [컴공과고씨] (0) | 2022.10.26 |
백준 5639 이진 검색 트리(linked list 활용) c++ [컴공과고씨] (0) | 2022.10.22 |