백준 다리놓기 1010 C++

 

 

우선 먼저 했던 코드부터 올려보자면

 

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;


int main() {
	

	int t = 0;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		vector <int> b_b;
		a = min(a, b-a);
		unsigned long long int sum = 1;
		for (int q = 1; q <= a; q++) {
			b_b.push_back(q);
		}
		for (int u = a; u >= 1; u--) {
			sum = sum * b;
			for (int k = 0; k < a; k++) {
				if (sum% b_b[k] == 0 && b_b[k] != 1) {
					sum = sum / b_b[k];
					b_b[k] = 1;
				}
			}
			b--;
		}
		cout << sum << '\n';
	}

	return 0;
}

예제는 다 돌아가지만, 결국 타임 에러가 뜨는 문제이다. 

 

이 문제를 풀기 위해서는 다른 다양한 방법이 있지만 

나는 DP와 파스칼 삼각형을 이용한  방법을 사용해서 풀어봤다.

 

 

 

 

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

int func(int, int);

int main() {
	
	
	int t = 0;
	cin >> t;
	memset(arr, -1, sizeof(arr));
	for (int i = 0; i < t; i++) {
		
		int a, b;
		int sum = 0;
		cin >> a >> b;
		sum = func(b,a);

		cout << sum << '\n';
	}

	return 0;
}
int func(int n, int m) {
	m = min(m, n - m);
	if (n == m) return 1;
	if (m == 0)return 1;
	if (m == 1) return n;
	if (arr[n][m] != -1) return arr[n][m];
	arr[n][m] = func(n - 1, m) + func(n - 1, m - 1);
	return arr[n][m];
}

func의 함수 내용은 조합의 성질을 나타냈다. 

n과 m의 계수가 같으면 1을 반환

m이 0이 될일이 없지만, 0이 된다면 1을 반환

m이 1이면 1을 n을 반환 그리고 그 값들을 배열에 넣어서 다음에도 사용할 기회가 있다면, 사용하도록 

배열에 그 값을 넣어줍니다.(배열은 초기에 한 번만 초기화시키면 됨)

 

이렇게 dp를 통해서 문제를 한번 풀어봤습니다.