오늘 푼 문제

https://www.acmicpc.net/problem/1010

다리놓기

• 풀이 방식
  일반적인 dp방식을 사용했다.
  다음에서 주의해야할 조건은 항상 동쪽의 지점이 서쪽의 지점보다 개수가 많다는 것이다.

- 서쪽이 1개일때, 동족의 개수가 N개라면 N개의 경우의 수 
- 서쪽의 개수가 N개, 동쪽의 개수가 N개면 항상 1개의 경우의 수

나의 풀이

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> v(30, vector<int>(30, 0));

void function() {
	v[0][0] = 0;
	for (int i = 1; i < 30; i++) {
		v[1][i] = i;
		v[i][i] = 1;
	}

	for (int i = 2; i < 30; i++) {
		for (int k = i; k < 30; k++) {
				v[i][k] = v[i - 1][k - 1] + v[i][k - 1];
		}
	}
}

int main() {

	int T, N, M;

	function();

	cin >> T;

	for (int i = 0; i < T; i++) {

		cin >> N >> M;
		cout << v[N][M] << endl;
	}

	return 0;
}

• 다른풀이법

#include <iostream>

using namespace std;

int main() {
    int num;
    cin >> num;
    while (num--) {
        int n, m;
        cin >> n >> m;
        
        long long ans = 1;
        
        int r = 1;
        for (int i = m; i > m - n; i--) {
            ans *= i;
            ans /= r++;
        }
        
        cout << ans << '\n';
    }
}

-> 통계 부분에서 조합을 사용하여 푸는 방식이 있는데 확실히 코드가 간편해진다. 수학적인 지식을 활용하는 것도 코드 짜는데 있어 중요해보인다..