2024-02-25

-동물원(12907, Baekjoon)

 규칙을 찾아 조건에 맞게 구현하는 간단한 문제였다. 동물의 종류는 토끼와 고양이밖에 없음으로, 똑같은 숫자가 2개를 넘어선 안되며, 0부터 연속하여 1씩증가하는 수로만 이루어져 있어야한다.(0, 1, 2, 3, 5같은 경우는 중간에 4가 빠져서, 안됨) 나는 입력받은 수들중 가장 큰 수를 mx변수에 담았다. 0부터 mx까지 반복하며, 한번도 나오지않은 수가있다면, 0 출력, 그전수보다 현재수가 더 많이(0, 1, 1 같이 0이 1번, 1이 2번나와 자신보다 1작은수의 개수보다 자신의 개수가 많은 경우는 불가능하다)나왔다면, 0을 출력하였다. 모두 처리 후, 남은 수들로 만들 수 있는 조합을 구하였다.

<소스코드>

#include <stdio.h>
#include <cmath>

int n;
int cnt[45];

int main()
{
	int i, j;
	int mx = -2e9;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		if (x > mx) mx = x;
		cnt[x]++;
	}
	int ans = 0, ct = 0;
	for (i = 0; i <= mx; i++) {
		if (cnt[i] > 2) {
			printf("0");
			return 0;
		}
		else if (i > 0 && cnt[i] > cnt[i - 1]) {
			printf("0");
			return 0;
		}
		else {
			if (cnt[i] == 2) ans++;
			else if (cnt[i] == 1) ct = 1;
		}
	}
	ans += ct;
	int res = pow(2, ans);
	printf("%d", res);
	return 0;
}

-거짓말(1043, Baekjoon)

 BFS를 이용하여 풀었다. 지민이가 거짓말을 할 수 있는 파티의 개수의 최댓값을 구하는 문제이다. 파티에 나온 사람들을 서로 이어주는 그래프를 만들고, 진실을 아는 사람을 기준으로 BFS탐색을 하여, 갈수있는 노드라면 check를 하여준 후, 파티들을 순회하며, check가 한번도 되지않은 사람들만있는 청결(?)한 파티라면 ans를 증가시켜 주는 식으로 풀었다. 풀고 난 뒤 기여를 하며 보니 유니온 파인드가 정해인듯 싶어 다음엔 유니온파인드로 풀어보려고 한다.

<소스코드>

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

using namespace std;

int n, k, m;
int arr[55];
vector <int> vec[55], as[55];
int ans, che[55];

void BFS(int x)
{
	int i, j;
	queue <int> q;
	q.push(x);
	che[x] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i];
			if (che[nw] == 0) {
				che[nw] = 1;
				q.push(nw);
			}
		}
	}
}

int main()
{
	int i, j;
	scanf("%d %d %d", &n, &m, &k);
	for (i = 0; i < k; i++) scanf("%d", &arr[i]);
	for (i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		for (j = 0; j < x; j++) {
			int y;
			scanf("%d", &y);
			as[i].push_back(y);
		}
		for (j = 0; j < x; j++) {
			for (int ij = 0; ij < x; ij++) {
				if (j == ij) continue;
				vec[as[i][j]].push_back(as[i][ij]);
			}
		}
	}
	for (i = 0; i < k; i++) {
		BFS(arr[i]);
	}
	for (i = 0; i < m; i++) {
		int l = as[i].size();
		int ch = 0;
		for (j = 0; j < l; j++) {
			if (che[as[i][j]] == 1) ch = 1;
		}
		if (ch == 0) ans++;
	}
	printf("%d", ans);
	return 0;
}

-퇴사 2 (15486, Baekjoon)

 간단한 DP문제였다. 1일차에서부터 차근차근 올라가는 식으로 간단히 풀 수 있는데, 점화식은 바로 떠올렸으나, n범위를 벗어나는 처리를 하다가 몇번 실수해서 그냥 날려버렸더니 맞았다.(?)

>점화식<

dp[i + t[i] - 1] = max(dp[i + t[i] - 1], dp[i - 1] + p[i])

<소스코드>

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

using namespace std;

int n;
int dp[1500010];
int t[1500010], p[1500010];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) scanf("%d %d", &t[i], &p[i]);
	for (i = 1; i <= n; i++) dp[i] = -2e9;
	for (i = 1; i <= n; i++) {
		dp[i] = max(dp[i - 1], dp[i]);
		dp[i + t[i] - 1] = max(dp[i + t[i] - 1], dp[i - 1] + p[i]);
	}
	printf("%d", dp[n]);
	return 0;
}

-자두나무 (2240, Baekjoon)

 간단한 DP문제이다. 문제의 n범위가 지나치게 작기때문에, 3차원 Dp로 풀었다. Dp[i][j][k] = i초가 지난 시점에서 j번 움직여, k번나무밑에 있을때 지금까지 받은 자두의 개수로 정의하고 풀었다. 처음에 1번나무 밑에 있다는 조건을 생각하지 않고, 2차원 Dp로 풀려다가 틀린후, 조건을 본뒤 3차원 Dp로 수정하였다.

>점화식<

dp[i][j][1] = dp[i - 1][j][1];
dp[i][j][2] = dp[i - 1][j][2];
if (j > 0) {
    if (arr[i] == 1) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][2]);
    if (arr[i] == 2) dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j - 1][1]);
}
dp[i][j][arr[i]]++;

<소스코드>

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

using namespace std;

int n, m;
int arr[1010];
int dp[1010][35][5];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);

	if (arr[0] == 1) dp[0][0][1] = 1;
	else dp[0][1][2] = 1;

	for (i = 1; i < n; i++) {
		for (j = 0; j <= m; j++) {
			dp[i][j][1] = dp[i - 1][j][1];
			dp[i][j][2] = dp[i - 1][j][2];
			if (j > 0) {
				if (arr[i] == 1) dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j - 1][2]);
				if (arr[i] == 2) dp[i][j][2] = max(dp[i][j][2], dp[i - 1][j - 1][1]);
			}
			dp[i][j][arr[i]]++;
		}
	}

	int ans = -2e9;
	for (i = 0; i <= m; i++) ans = max(ans, max(dp[n - 1][i][1], dp[n - 1][i][2]));
	printf("%d", ans);
	return 0;
}

-캠핑 (4796, Baekjoon)

 매우 쉬운 수학 문제이다. P일중 L일동안만 사용이 가능함으로, 휴가일수에서 P로나눈뒤 그 몫을 L로 곱한값에 V를 P로 나눈 나머지를 더하면 된다. 하지만 이 경우, L보다 V%P가 커지는 경우가 있는데 이는 따로 처리하여주면 된다.

#include <stdio.h>

int main()
{
	int t = 1;
	while (1)
	{
		int L, P, V;
		scanf("%d %d %d", &L, &P, &V);
		if (L == 0 && P == 0 && V == 0) break;
		int res;
		if ((V % P) > L) res = L;
		else res = (V % P);
		printf("Case %d: %d\n", t, (L * (V / P)) + res);
		t++;
	}
	return 0;
}