BOJ - 다리놓기(1010)

실버4 : 메모이제이션 문제이다.

생각

고등학교 때 많이 풀어본 함수의 개수 구하는 문제와 같다. 결국은 공역단에서 N개의 site를 고르게 되면 자동으로 순서가 결정되기 때문이다. M개의 원소 중에 N개의 원소를 고르면 되는 문제이기 때문에 이것은 결국 조합을 구현하는 문제와 같다. 그 과정에서 중복되는 조합 값이 존재하기 때문에 이것을 따로 저장하게 되면 시간이 매우 많이 단축된다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
ll memo[31][31];
 
ll combination(int M, int N){
    if (M == N || N == 0) return 1;
    if (memo[M-1][N-1] == 0) memo[M-1][N-1] = combination(M-1, N-1);
    if (memo[M-1][N] == 0) memo[M-1][N] = combination(M-1, N);
    return memo[M-1][N-1] + memo[M-1][N];
}
 
int main(){
    int T;
    cin >> T;
    for (int tc = 0; tc < T; tc++) {
        int N, M;
        cin >> N >> M;
        cout << combination(M, N) << '\n';
    }
}
 

Reference

• 백준(1010번) - 소수