한 문장으로 끝나는 아주 깔꼼한 문제
문제는 여기서 확인할 수 있다. BaekJoon #2407. 조합
💀 시행착오
👇 풀이를 보러 온거라면 아래에 POINT로 바로 내려가면 된다. 👇
일단 n!/m!(n-m!)을 그냥 계산하면 범위가 오버되니까 파스칼 삼각형으로 계산해야겠다는 생각이 들었다. 그런데 n, m 범위가 100까지...? 범위가 어디까진거지.. 하고 계산기를 뚜드려봤더니
n=100, m=50을 기준으로 약 30자리의 결과값이 나온다.
long long 타입도 8byte이기 때문에 2^32, 약 19자리 정도 연산이 가능하다.
그러면 10^15정도에서 잘라서 두 배열에 쪼개서 담으면 되지 않을까...? 하는 생각을 했다. 그런데 1000000000000005 뭐 이런 값이 나와서 중간에 잘렸는데 0이 몇개인지 모른다면(암튼 뭐) 대충 이런 생각하다가 이러느니 string으로 계산하겠다!!!! 하고 넘어갔다. 다행히 맞는 방법이었다.
🤔 POINT
1. 파스칼의 삼각형
조합 문제는 파스칼의 삼각형을 재귀함수로 구현하면 쉽게 코드를 작성할 수 있다. string 배열 comb[][]에 조합을 구하는 중간 값을 저장해서 계산에 중복이 없도록 했다.
string make_comb(int n, int m){
// nCm = nC(m-n)
if(m*2 > n) m = n-m;
// nC0 = 1, nC1 = n
if(m==0){
comb[n][m] = "1";
check[n][m] = true;
}
else if(m==1) {
comb[n][m] = to_string(n);
check[n][m] = true;
}
// 이미 구한 값이면 comb 값
if(check[n][m]) {
return comb[n][m];
}
else{
// 없는 값은 재귀함수로
string first_comb = make_comb(n-1, m-1);
string second_comb = make_comb(n-1, m);
comb[n][m] = str_plus(first_comb, second_comb);
check[n][m] = true;
return comb[n][m];
}
}2. string 숫자 연산
두 string을 받아서 일단 뒤집어준다. 둘의 길이가 다르기 때문에 인덱스 0부터 올라가기 위함이다. 한자리씩 더해주는데 이때 올라가는 값만 잘 처리해주면된다.
string의 길이가 다른 거는 연산을 시작하기 전에 s1의 길이가 더 긴 것으로 되도록 swap_str() 함수를 만들었다.
// s1이 더 긴 string이 되도록 swap
void swap_str(string &s1, string &s2){
int s1_len = s1.length();
int s2_len = s2.length();
if(s1_len >= s2_len) return;
string temp = s1;
s1 = s2;
s2 = temp;
return;
}
// 두 string의 정수 덧셈 연산
string str_plus(string s1, string s2){
string new_s = "";
swap_str(s1, s2);
int s1_len = s1.length();
int s2_len = s2.length();
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
int num1, num2, sum, upnum = 0;
for(int i=0; i<s1_len; i++){
num1 = s1[i] - '0';
if(i < s2_len) num2 = s2[i] - '0';
else num2 = 0;
sum = num1+num2+upnum;
if(sum>=10){
upnum = 1;
sum -= 10;
} else upnum = 0;
new_s += (sum + '0');
}
if(upnum == 1) new_s += '1';
reverse(new_s.begin(), new_s.end());
return new_s;
}3. 전체 코드
전체 코드는 아래와 같다.
//BaekJoon_2407
//조합
/*
* 제한 시간 : 2s
* 정답 비율 : 34.485%
*/
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
string comb[105][55];
bool check[105][55] = {false,};
// s1이 더 긴 string이 되도록 swap
void swap_str(string &s1, string &s2){
int s1_len = s1.length();
int s2_len = s2.length();
if(s1_len >= s2_len) return;
string temp = s1;
s1 = s2;
s2 = temp;
return;
}
// 두 string의 정수 덧셈 연산
string str_plus(string s1, string s2){
string new_s = "";
swap_str(s1, s2);
int s1_len = s1.length();
int s2_len = s2.length();
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
int num1, num2, sum, upnum = 0;
for(int i=0; i<s1_len; i++){
num1 = s1[i] - '0';
if(i < s2_len) num2 = s2[i] - '0';
else num2 = 0;
sum = num1+num2+upnum;
if(sum>=10){
upnum = 1;
sum -= 10;
} else upnum = 0;
new_s += (sum + '0');
}
if(upnum == 1) new_s += '1';
reverse(new_s.begin(), new_s.end());
return new_s;
}
string make_comb(int n, int m){
// nCm = nC(m-n)
if(m*2 > n) m = n-m;
// nC0 = 1, nC1 = n
if(m==0){
comb[n][m] = "1";
check[n][m] = true;
}
else if(m==1) {
comb[n][m] = to_string(n);
check[n][m] = true;
}
// 이미 구한 값이면 comb 값
if(check[n][m]) {
return comb[n][m];
}
else{
// 없는 값은 재귀함수로
string first_comb = make_comb(n-1, m-1);
string second_comb = make_comb(n-1, m);
comb[n][m] = str_plus(first_comb, second_comb);
check[n][m] = true;
return comb[n][m];
}
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
string result = make_comb(n, m);
cout << result.c_str() << endl;
return 0;
}덧.
- 나는 C++을 사용했지만 Python은
Big Integer를 내부적으로 제공한다. - 가장 처음에
long long두개를 이용한 풀이를 생각했다가string구현이 쉽다고 판단했지만long long으로 구현할 수도 있다. 있더라고요... 나는 string을 쓰겠어.. 자릿수 고민하다 실수해버릴 것 같다..
주저리
나홀로 solved.ac 챌린지를 하겠다고 당당히 글을 쓰고 이제야 총 몇문제인가 했더니 120문제가 넘는다. 그 중 플라티늄 문제는 20문제가 넘는다. 나는 망했다.
끝 ✌
