일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 알고리즘 풀이
- django widget
- es6
- react
- 파이썬
- 알고리즘
- web
- 백준
- Git
- django ORM
- form
- MAC
- js
- PYTHON
- 파이썬 알고리즘
- Baekjoon
- Django
- AWS
- java
- django rest framework
- HTML
- 알고리즘 연습
- Algorithm
- API
- javascript
- 장고
- 알고리즘 문제
- c++
- DRF
- CSS
Archives
- Today
- Total
수학과의 좌충우돌 프로그래밍
[C++] BAEKJOON 2407 조합 본문
https://www.acmicpc.net/problem/2407
문제는 아주 간단합니다.
Combination을 계산하는 문제로, 파스칼 삼각형을 이용하여 문제를 해결하려 하였습니다.
그런데 n, m의 값이 커지면 unsigned long long으로도 데이터를 전부 표현할 수 가 없어 덧셈을 문자열로 구현하였습니다.
#include <iostream>
#include <string>
using namespace std;
// nCm : pascal[i][j]
string pascal[101][101];
string add_string_num(string a, string b)
{
int aidx = a.size() - 1;
int bidx = b.size() - 1;
string result = "";
int carry = 0;
while (aidx >= 0 && bidx >= 0)
{
int temp = a[aidx--] - '0' + b[bidx--] - '0' + carry;
//int temp = stoi("123");
result = to_string(temp % 10) + result;
carry = temp / 10;
}
while (aidx >= 0)
{
int temp = a[aidx--] - '0' + carry;
result = to_string(temp % 10) + result;
carry = temp / 10;
}
while (bidx >= 0)
{
int temp = b[bidx--] - '0' + carry;
result = to_string(temp % 10) + result;
carry = temp / 10;
}
if (carry)
result = to_string(carry) + result;
return result;
}
int main()
{
int n, m;
cin >> n >> m;
pascal[0][0] = "1";
for (int i = 1; i < 101; i++)
{
for (int j = 0; j < i + 1; j++)
{
if (j - 1 >= 0)
pascal[i][j] = add_string_num(pascal[i - 1][j - 1], pascal[i - 1][j]);
else
pascal[i][j] = pascal[i - 1][j];
}
}
cout << pascal[n][m] << "\n";
}
'알고리즘 > C++' 카테고리의 다른 글
[C++] stl container set, multiset (0) | 2020.04.14 |
---|---|
[C++] string 문자열 나누는 split (3) | 2020.03.15 |
[C++] BAEKJOON 17968 Fire on Field (acm-icpc) (0) | 2019.11.13 |
[C++] BAEKJOON 11404 플로이드 (0) | 2019.11.10 |
[C++] BAEKJOON 11559 Puyo Puyo (0) | 2019.11.04 |
Comments