2024-03-09

 

-다리 놓기(1010, 백준)

 왼쪽 사이트와 오른쪽 사이트사이에 다리를 겹치치 않고 지으려 했을때 가능한 방법의 수를 구하는 문제이다. 몇번 구하다보면 규칙을 발견 할 수있는데, 더 많은 오른쪽 사이트에서 왼쪽사이트를 골랐을 때, 나머지 다리가 더 적은 다리를 구할 수 있게 됨으로 조합으로 나타낼 수 있다. 결국 mCn을 구하는 문제.

<소스 코드>

#include <stdio.h>

long long dp[1010][1010];

int main()
{
	int i, j;
	int t;
	dp[0][0] = 1;
	for (i = 1; i <= 30; i++) {
		for (j = 0; j <= 30; j++) {
			if (j > 0) dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]);
			else dp[i][j] = 1;
		}
	}
	scanf("%d", &t);
	while (t--) {
		int n, m;
		scanf("%d %d", &n, &m);
		printf("%lld\n", dp[m][n]);
	}
	return 0;
}

-조약돌 꺼내기(13251, 백준)

 간단한 확률 문제이다. 전체 색상을 탐색해가며, 전체 조약돌 중, 현재 색깔에 해당하는 조약돌을 뽑을 확률을 구한뒤 ans에 더해가며 구해주면 되는 간단한 문제이다.

<소스 코드>

#include <stdio.h>
#include <algorithm>

int n, k, sum, arr[55];
double ans;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]), sum += arr[i];
	scanf("%d", &k);
	if (n == 1 || k == 1) {
		printf("1.0");
		return 0;
	}
	double now = 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j < k; j++) {
			now *= ((double)arr[i] - j) / ((double)sum - j);
		}
		ans += now;
		now = 1;
	}
	printf("%.16lf", ans);
	return 0;
}

-수열의 순서(1722, 백준)

 모든 순열을 출력하면 총 20!임으로 시간초과가 난다. 따라서 경우를 나눠 각각 구해주면 된다. 

i) Query 1 -> 맨앞에서부터 탐색한다. 현재 N자리값이라면 (N-1)!보다 작아질때까지 (N-1)!을 빼주며 idx를 증가시켜준뒤, 해당 자리값에 저장해 준다.

ii) Query 2 -> 지금까지 쓰지않은 수중, 현재값을 찾을 때 까지 idx를 증가시켜준뒤, idx에 (N-1)!을 곱한값을 더해준뒤 모두 더한 수를 출력.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

long long facto[25];
int n, k;
int ch[25];

int main()
{
	int i, j;
	scanf("%d %d", &n, &k);
	facto[0] = 1;
	for (i = 1; i <= n; i++) facto[i] = facto[i - 1] * i;
	if (k == 2) {
		long long ans = 0;
		vector <int> vec;
		for (i = 0; i < n; i++) {
			int x;
			scanf("%d", &x);
			vec.push_back(x);
		}
		for (i = 0; i < vec.size() - 1; i++) {
			int idx = 0;
			for (j = 1; j <= n; j++) {
				if (ch[j] == 1) continue;
				if (j == vec[i]) break;
				idx++;
			}
			ch[vec[i]] = 1;
			ans += (idx) * facto[n - i - 1];
		}
		printf("%lld", ans + 1);
	}
	else if (k == 1) {
		long long num;
		scanf("%lld", &num);
		vector <int> ans;
		for (i = 1; i <= n; i++) {
			int idx = 0;
			vector<int> now;
			for (j = 1; j <= n; j++) {
				if (ch[j] == 0) now.push_back(j);
			}
			if (num <= facto[n - i]) idx = 0;
			else {
				while (1) {
					num -= facto[n - i];
					idx++;
					if (num <= facto[n - i]) break;
				}
			}
			ans.push_back(now[idx]);
			ch[now[idx]] = 1;
			now.clear();
		}
		for (i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
	}
	return 0;
}

-게임 개발(1516, 백준)

 간단한 위상정렬 문제이다. ACM 크래프트와 비슷한 문제였다. 전 단계중 항상 최댓값이 현재작업을 시작하는 값임으로, 이를 저장해가며 위상정렬을 해주면 된다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

int n;
int dis[510], time[510];
int ent[510];
vector<int> vec[510];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &time[i]);
		while (1) {
			int x;
			scanf("%d", &x);
			if (x == -1) break;
			vec[x].push_back(i);
			ent[i]++;
		}
	}
	queue<int> q;
	for (i = 1; i <= n; i++) {
		dis[i] = time[i];
		if (ent[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i];
			ent[nw]--;
			if (ent[nw] == 0) {
				q.push(nw);
			}
			dis[nw] = max(dis[now] + time[nw], dis[nw]);
		}
	}
	for (i = 1; i <= n; i++) printf("%d\n", dis[i]);
	return 0;
}

-선물 전달(1947, 백준)

 보는 순간 교란순열(완전 순열)이라고 생각했다. 자기 자신을 제외한 다른 수들과 대응해야함으로 (n-1)을 곱해준다.이때 수 n이 k에 대응 해야된다 할때 두가지 방법이 생긴다.

i) k, n이 짝을 이루고 나머지 수들이 쌍을 이루게 되는 경우 - > Dp[n-2]

ii) k, n이 대응하지 않고, k와 n을 같게 보는 경우 -> Dp[n-1]

과 같이 점화식을 세울 수 있으며, Dp문제이다.

>점화식<

Dp[i] = (i - 1) * (Dp[i-2] + Dp[i-1])

<소스 코드>

#include <stdio.h>

int n;
long long dp[1000010];

int main()
{
	int i, j;
	scanf("%d", &n);
    dp[2] = 1;
	dp[3] = 2;
	dp[4] = 9;
	for (i = 5; i <= n; i++) {
		dp[i] = ((i - 1) % 1000000000 * (dp[i - 1] + dp[i - 2]) % 1000000000);
	}
	printf("%lld", dp[n]);
	return 0;
}