2024-03-11

-방배정(13304, 백준)

 간단 한 문제이다. {1~2학년 남녀}, {3~4학년 남}, {3~4학년 여}, {5~6학년 남}, {5~6학년 여}그룹으로 나누어 풀면 된다. 입력 받은수가 어느 그룹에 속하는지를 확인하고 구하면 풀린다.

<소스 코드>

#include <stdio.h>

int low, mid_ma, mid_fe, high_ma, high_fe;
int n, k;

int main()
{
	int i, j;
	scanf("%d %d", &n, &k);
	for (i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &y, &x);
		if (1 <= x && x <= 2) low++;
		else if (3 <= x && x <= 4) {
			if (y == 1) mid_ma++;
			else mid_fe++;
		}
		else if (5 <= x && x <= 6) {
			if (y == 1) high_ma++;
			else high_fe++;
		}
	}
	int ans = (low / k) + (mid_ma / k) + (mid_fe / k) + (high_ma / k) + (high_fe / k);
	if (low % k > 0) ans++;
	if (mid_ma % k > 0) ans++;
	if (mid_fe % k > 0) ans++;
	if (high_ma % k > 0) ans++;
	if (high_fe % k > 0) ans++;
	printf("%d", ans);
	return 0;
}

-주유소(13305, 백준)

 그리디 문제이다. 앞에서부터 최솟값을 갱신해주며 최솟값에 거리를 곱해주었다.

<소스 코드>

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

using namespace std;

long long n;
long long val[100010], way[100010];
long long ans;

int main()
{
	long long i, j;
	scanf("%lld", &n);
	for (i = 1; i < n; i++) scanf("%lld", &way[i]);
	for (i = 1; i <= n; i++) scanf("%lld", &val[i]);
	long long mn = 2e9;
	for (i = 1; i < n; i++) {
		mn = min(mn, val[i]);
		ans += mn * way[i];
	}
	printf("%lld", ans);
	return 0;
}

-리조트(13302, 백준)

 2차원 DP문제이다. 간단하게 생각하고 풀었다가 한참 고민했던 문제였다. Dp[i][j] = j개의 쿠폰을 갖고 i일까지의 최솟값으로 두고 푼다. 경우를 나누어 풀면 쉽게 풀 수 있다.

1) 리조트에 가지않는 날

2) 1일권을 사는 경우

3) 3일권을 사는 경우

4) 5일권을 사는 경우

3일권과 5일권을 사용중일때, 또 이용권을 사는 반례가 있음에 주의하자.

>점화식<

1) dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
2) dp[i + 1][j] = min(dp[i][j] + 10, dp[i + 1][j]);

3) for (int l = 1; l <= 3; l++) dp[i + l][j + 1] = min(dp[i][j] + 25, dp[i + l][j + 1]);

4) for (int l = 1; l <= 5; l++) dp[i + l][j + 2] = min(dp[i][j] + 37, dp[i + l][j + 2]);

<소스 코드>

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

using namespace std;

int n, m;
int ch[110];
int dp[210][210];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		ch[x] = 1;
	}
	if (n == m) {
		printf("0");
		return 0;
	}
	for (i = 0; i <= n + 5; i++) {
		for (j = 0; j <= n + 5; j++) {
			dp[i][j] = 2e9;
		}
	}
	dp[0][0] = 0;
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= n; j++) {
			if (dp[i][j] == 2e9) continue;
			if (ch[i + 1] == 1) dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
			dp[i + 1][j] = min(dp[i][j] + 10, dp[i + 1][j]);
			if (j >= 3) dp[i + 1][j - 3] = min(dp[i + 1][j - 3], dp[i][j]);
			for (int l = 1; l <= 3; l++) dp[i + l][j + 1] = min(dp[i][j] + 25, dp[i + l][j + 1]);
			for (int l = 1; l <= 5; l++) dp[i + l][j + 2] = min(dp[i][j] + 37, dp[i + l][j + 2]);
		}
	}
	int ans = 2e9;
	for (i = 0; i <= n; i++) ans = min(ans, dp[n][i]);
	long long res = ans * 1000;
	printf("%lld", res);
	return 0;
}

-상자넣기(1965, 백준)

 문제를 읽으면 누가봐도 LIS이다. LIS를 알면 아주 쉽게 풀린다. O(n^2)으로도 풀림 

<소스 코드>

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

using namespace std;

int n;
int arr[1010];
vector <int> lis;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	lis.push_back(arr[0]);
	for (i = 1; i < n; i++) {
		int lb = lower_bound(lis.begin(), lis.end(), arr[i]) - lis.begin();
		int sz = lis.size();
		if (lb >= sz) lis.push_back(arr[i]);
		else lis[lb] = arr[i];
	}
	printf("%d", lis.size());
	return 0;
}

-동물원(1309, 백준)

 규칙 찾다가 뒤에 비어있는게 예외처리가 되길래 배열 2개로 풀어서 합쳤다. Dp[i][0] = 끝의 칸이 비어있는 경우 Dp[i][1] = 끝의 칸이 채워져있는 경우로 두고 구현해 풀었다. 1차원으로도 쉽게 풀린덴다.(뇌가 멍청해진 것같다.)

>점화식<

dp[i][0] = (dp[i - 1][0] + dp[i - 1][1])

dp[i][1] = (dp[i - 1][0] * 2 + dp[i - 1][1])

<소스 코드>

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

using namespace std;

int dp[100010][2];
int n;

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