-
알고리즘: 백준 1010번 다리놓기 (feat. c++)알고리즘/백준(BaekJoon) 2020. 8. 18. 19:00
백준 1010번 링크입니다.
n개 중에 r개를 고르면 되므로 nCr을 사용하면 간단하다...고 생각했지만
아니였다.
팩토리얼을 다이나믹 프로그래밍으로 구해서 콤비네이션하려 했지만
long long 자료형을 써도 넘어가버려서
다이나믹 프로그래밍과 재귀함수를 이용하였다.
nCr = n-1Cr-1 + n-1Cr 을 이용해서
recursive form을 만들어 해결하였다.
#include<iostream> using namespace std; int cache[30][30]; // 다이나믹 프로그래밍의 테이블 int recurseive_comb(int n, int r) {//recursuve form if (n == r) { //base case return 1; } else if (r == 0) { return 1; } else if (r == 1) { return n; } // 만약 값이 존재하면 바로 리턴 if (cache[n][r] != NULL) { return cache[n][r]; } //값이 존재하지 않는다면 재귀를 이용해서 값을 만들어준다. cache[n][r] = recurseive_comb(n - 1, r - 1) + recurseive_comb(n - 1, r); return cache[n][r]; } int main() { int T; cin >> T; int** cases = new int*[T]; for (int i = 0; i < T; i++) { cases[i] = new int[2]; cin >> cases[i][0]; cin >> cases[i][1]; } for (int i = 0; i < T; i++) { cout << recurseive_comb(cases[i][1], cases[i][0])<<endl; } return 0; }
반응형'알고리즘 > 백준(BaekJoon)' 카테고리의 다른 글
알고리즘: 백준 1697번 숨바꼭질 (feat. c++) (0) 2020.08.23 알고리즘: 백준 2667번 단지번호붙이기 (feat. c++) (0) 2020.08.22 알고리즘: 백준 1018번 체스판 다시칠하기(feat. c++) (0) 2020.08.18 알고리즘: 백준 1037번 약수(feat. c++) (0) 2020.08.18 알고리즘: 백준 10610번 30 (feat. Python) (0) 2020.08.08