Doby's Lab

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 n r이 nCr이라는 것을 알면 예전에 풀었던 문제와 똑같이 풀린다. 다른 점은 나머지 정리(MOD == 10007)로 인해 문자열의 합을 구할 필요 없다는 점이었다. (콤비네이션 예전 포스팅 https://draw-code-boy.tistory.com/101) [AC 코드] #include #include #define MOD 10007 using namespace std; int cache[1001][1001]; int combi(int n, int r..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리를 잇는 경우가 고등학생 때 배우던 조합론: 콤비네이션을 기억해낼 수 있다면 풀릴 수 있는 문제였다. 시간도 0.5초로 짧아서 탑 다운 DP형식으로 구현을 했고 범위는 30 이전이라 문자열의 합은 구현하지 않아도 될 거 같았다. 콤비네이션에 관한 문제를 예전에 풀고, 포스팅해놓았어서 쉽게 풀렸다. https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번:..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생 때 배웠던 nCr 개념이 등장한다. 정확히는 n Combination r이라고 부른다. 이와 같이 따라오는 게 nPr로 이는 n Permutation r이라고 부른다. 이 둘은 조합론으로 둘 다 공식이 존재한다. 솔루션 1 (실패) 이 공식을 활용하여 두 개의 팩토리얼 함수를 구현하여 풀려고 했다. [조금 다른 방식의 팩토리얼 함수] 각각 n!, (n - r)!, r! 은 시간이 오래 걸릴뿐더러 숫자까지 너무 커질 ..