2024-03-02

-돌 게임(9655, 백준)

 간단한 DP문제였다. 그냥 마지막 돌을 가져간 사람이 이김으로, 마지막 돌을 1로 두고 마지막 돌애서부터 1개 또는 3개 전의 돌을 가져가면 지게 됨으로 0으로 두는 식으로 점화식을 세우면 O(N)만에 풀 수 있다. 처음에는 수학적으로 접근하다가 N범위가 적은걸 보고 그냥 DP돌렸다. 수학으로도 풀린다는 소문이있다. 

>점화식<

if (dp[i + 1] == 0) dp[i] = 1;

else if (dp[i + 1] == 1) dp[i] = 0;

if (dp[i + 3] == 0) dp[i] = 1;

<소스코드>

#include <stdio.h>

int n;
int dp[1010];

int main()
{
	int i, j;
	scanf("%d", &n);
	dp[n] = 1;
	for (i = n - 1; i >= 1; i--) {
		if (dp[i + 1] == 0) dp[i] = 1;
		else if (dp[i + 1] == 1) dp[i] = 0;
		if (i <= n - 3) {
			if (dp[i + 3] == 0) dp[i] = 1;
		}
	}
	if (dp[1] == 1) printf("SK");
	else printf("CY");
}

-기타 레슨(2343, 백준)

 N범위 보고 문제보면 누가봐도 이분탐색문제이다. 숫자구슬이라는 문제랑 비슷하게 풀었던것같다. mid = 블루레이의 최대 용량으로 두고, 이때의 저장하기 위해 필요한 블루레이의 수를 mid_res로 두고, mid_res를 이용해 이분탐색을 진행 한뒤, 최소값을 구해야 함으로, low를 출력하면 된다.

<소스코드>

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

using namespace std;

long long n, m;
long long arr[100010];

long long pand(long long x)
{
	long long i, ans = 0;
	long long s = 0;
	for (i = 0; i < n; i++) {
		if (s + arr[i] > x) {
			ans++;
			s = arr[i];
		}
		else s += arr[i];
	}
	return ans;
}

int main()
{
	long long i, j;
	scanf("%lld %lld", &n, &m);
	long long low = -2e9, high = 0;
	for (i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
		high += arr[i];
		if (low < arr[i]) low = arr[i];
	}
	while (low <= high)
	{
		long long mid = (low + high) / 2;
		long long mid_res = pand(mid);
		if (mid_res < m) high = mid - 1;
		else low = mid + 1;
	}
	printf("%lld", low);
	return 0;
}

-Coins(3067, 백준)

 2차원 Dp문제였다. 어디선가 비슷한 문제를 푼 기억이 있는 것같은데, 기억은 안난다. Dp[i][j] = i종류까지의 동전만 이용해서 j원을 만드는 경우의 수로 풀었다. 1중 DP를 이용하면, 3 = 1 + 2, 3 = 2 + 1같이 겹치는 경우는 걸러내지 못해서, 2차원 Dp로 풀었다. 

>점화식<

dp[i][j] += dp[i - 1][j];

dp[i][j] += dp[i][j - vec[i]];

<소스코드>

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

using namespace std;

int dp[30][10010];

int main()
{
	int i, j;
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		vector <int> vec;
		for (i = 0; i < n; i++) {
			int x;
			scanf("%d", &x);
			vec.push_back(x);
		}
		int m;
		scanf("%d", &m);
		for (i = 0; i < n; i++) {
			for (j = 1; j <= m; j++) {
				dp[i][j] = 0;
			}
		}
		for (i = 0; i < n; i++) {
			dp[i][vec[i]] = 1;
			for (j = 1; j <= m; j++) {
				if (i > 0) dp[i][j] += dp[i - 1][j];
				if (j >= vec[i]) dp[i][j] += dp[i][j - vec[i]];
			}
		}
		/*for (i = 0; i < n; i++) {
			for (j = 1; j <= m; j++) {
				printf("%d ", dp[i][j]);
			}
			printf("\n");
		}*/
		printf("%d\n", dp[n - 1][m]);
	}
	return 0;
}

-가장 큰 정사각형(1915, 백준)

 2차원 Dp문제였다. 정 사각형이 만들어지는 규칙을 찾아야 한다. Dp 테이블을 채워보며 Dp[i][j] = i, j까지탐색했을 때의 정사각형의 최대 변의 길이로 정의하면 된다.

>점화식<

if (dp[i][j] == 1) dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;

<소스코드>

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

using namespace std;

int n, m;
int dp[1010][1010];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%1d", &dp[i][j]);
		}
	}
	for (i = 1; i < n; i++) {
		for (j = 1; j < m; j++) {
			int mn = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1]));
			if (dp[i][j] == 1) dp[i][j] = mn + 1;
		}
	}
	int ans = -2e9;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			ans = max(dp[i][j], ans);
		}
	}
	printf("%d", ans*ans);
	return 0;
}

-암호 코드(2011, 백준)

 숫자카드 문제를 풀었던 기억이 있어 쉽게 풀었다. 사이에 끼인 0만 어떻게 처리해준다면 피보나치 수열과 비슷한 느낌이다.

>점화식<

int x = s[i] - '0', y = s[i - 1] - '0';
if (x > 0) dp[i] = dp[i - 1];
if (y == 0) continue;
if (y * 10 + x <= 26) dp[i] = (dp[i] + dp[i - 2]);

<소스코드>

#include <stdio.h>
#include <string.h>

int n;
int dp[5010];
char s[5010];

int main()
{
	int i, j;
	scanf("%s", s + 1);
	s[0] = '0';
	if (s[1] == '0') {
		printf("0");
		return 0;
	}
	n = strlen(s) - 1;
	dp[0] = 1;
	dp[1] = 1;
	for (i = 2; i <= n; i++) {
		int x = s[i] - '0', y = s[i - 1] - '0';
		if (x > 0) dp[i] = dp[i - 1];
		if (y == 0) continue;
		if (y * 10 + x <= 26) dp[i] = (dp[i] + dp[i - 2]) % 1000000;
	}
	printf("%d", dp[n]);
	return 0;
}