2024-03-10

-쉬운 계단 수(10844, 백준)

 간단한 Dp문제이다. Dp[i][j] = 끝이 j로끝나는 i자리 계단 수의 개수로 두고 풀었다. 해보면 기본적으로, Dp[i] = 2 * Dp[i-1]이라는 식이 쉽게 나온다. 하지만 여기서 끝이 0 혹은 9로 끝나는 경우에만 예외가 생기가 되며, 이만 잘 처리해준다면 AC를 맞을 수 있다.

>점화식<

dp[i + 1][j + 1] = (dp[i+1][j+1] + dp[i][j])

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

<소스 코드>

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

using namespace std;

long long dp[110][10];
long long cnt[10];
int n;

int main()
{
	int i, j;
	long long mod = 1000000000;
	scanf("%d", &n);
	dp[0][9] = 1;
	for (i = 1; i <= 9; i++) dp[1][i] = 1;
	for (i = 1; i <= n; i++) {
		for (j = 0; j <= 9; j++) {
			if(j < 9) dp[i + 1][j + 1] = (dp[i+1][j+1] + dp[i][j]) % mod;
			if(j > 0) dp[i + 1][j - 1] = (dp[i+1][j-1] + dp[i][j]) % mod;
		}
	}
	long long ans = 0;
	for (i = 0; i <= 9; i++) ans = (ans + dp[n][i]) % mod;
	printf("%lld", ans);
	return 0;
}

-연속합 2(13398, 백준)

 수를 하나 없앨 수 있는 연속합 문제이다. dp[i][j] = j번 수를 지워서 i까지의 연속합의 최댓값으로 두고 풀었다. 0번 지우는 경우, 현재값과 그전값까지의 합중 최대를 정해 더해준다. 1번이상 지운다면, 현재값에서 지우는 경우와 뒤에 지운수에서 현재값을 더한 경우중 최대값으로 해주었다.

>점화식<

dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i]);

dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + arr[i]);

<소스 코드>

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

using namespace std;

long long dp[100010][5];
long long arr[100010];
long long n;

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

-LCS 2(9252, 백준)

 LCS의 기초문제이다. 2차원 dp를 잡아주고, i, j번째에 각 문자가 같은경우 dp[i-1][j-1]에서 1을 더한수를 가져오면 된다. 문제는 경로 탐색인데, 2차원 경로 배열을 잡아준 뒤, 1 => 위, 2 => 옆, 3 => 대각선으로 두고 경로를 저장한 뒤, 경로를 출력하면 된다.

>점화식<

if (dp[i - 1][j] > dp[i][j - 1]) {
	dp[i][j] = dp[i - 1][j];
	way[i][j] = 1;
}
else {
	dp[i][j] = dp[i][j - 1];
	way[i][j] = 2;
}
if (s1[i] == s2[j]) {
	if (dp[i][j] <= dp[i - 1][j - 1] + 1) {
		dp[i][j] = dp[i - 1][j - 1] + 1;
		way[i][j] = 3;
	}
}

<소스 코드>

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

using namespace std;

char s1[1010], s2[1010];
int l1, l2;
int dp[1010][1010];
int way[1010][1010]; // 1 => 위, 2 => 옆, 3 => 대각선
vector <char> ans;

void dfs(int x, int y)
{
	int wy = way[x][y];
	if (wy == -1) return;
	else if (wy == 1) dfs(x - 1, y);
	else if (wy == 2) dfs(x, y - 1);
	else {
		ans.push_back(s1[x]);
		dfs(x - 1, y - 1);
	}
}

int main()
{
	int i, j;
	scanf("%s", s1 + 1);
	scanf("%s", s2 + 1);
	s1[0] = '0', s2[0] = '0';
	l1 = strlen(s1);
	l2 = strlen(s2);
	for (i = 0; i < l1; i++) way[i][0] = -1;
	for (i = 0; i < l2; i++) way[0][i] = -1;
	for (i = 1; i < l1; i++) {
		for (j = 1; j < l2; j++) {
			if (dp[i - 1][j] > dp[i][j - 1]) {
				dp[i][j] = dp[i - 1][j];
				way[i][j] = 1;
			}
			else {
				dp[i][j] = dp[i][j - 1];
				way[i][j] = 2;
			}
			if (s1[i] == s2[j]) {
				if (dp[i][j] <= dp[i - 1][j - 1] + 1) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
					way[i][j] = 3;
				}
			}
		}
	}
	printf("%d\n", dp[l1 - 1][l2 - 1]);
	dfs(l1 - 1, l2 - 1);
	for (i = ans.size() - 1; i >= 0; i--) printf("%c", ans[i]);
	return 0;
}

-사전(1256, 백준)

 중복 조합 문제이다. 처음에는 중복 순열 문제인줄 알았는데, 중복순열은 너무 값이 커지기 때문에 중복 조합을 이용하여 풀었다. a사이에 비어있는 칸에 z를 끼워 넣는 경우를 생각해보면, 중복 조합을 이용하여 풀 수 있다. 자리수를 가장 앞자리 수부터 탐색해 나가면서, 앞자리 수에 a를 넣는 경우의 수를 계산 후, 계산값이 k보다 크다면 a를 넣고, 작다면 z를 넣고 k에서 해당 계산값을 빼주는 식으로 계산했다. N범위가 크기때문에 PYTHON이 아니라면 unsigned 64bit자료형을 이용해야 한다.

<소스 코드>

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

using namespace std;

unsigned long long dp[210][110];
unsigned long long n, m, k;
unsigned long long nx, ny;
vector <char> vec;

int main()
{
	unsigned long long i, j;
	scanf("%llu %llu %llu", &n, &m, &k);
	nx = n;
	ny = m;
	dp[0][0] = 1;
	for (i = 1; i <= n + m; i++) {
		for (j = 0; j <= m; j++) {
			if (j > 0) dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]);
			else dp[i][j] = 1;
		}
	}
	if (dp[n + m][m] < k) {
		printf("-1");
		return 0;
	}
	unsigned long long now = k;
	for (i = 0; i < n + m; i++) {
		unsigned long long now_com = dp[nx - 1 + ny][ny];
		if (now_com >= now) {
			nx--;
			vec.push_back('a');
		}
		else {
			ny--;
			vec.push_back('z');
			now -= now_com;
		}
	}
	for (i = 0; i < vec.size(); i++) printf("%c", vec[i]);
	return 0;
}

-최솟값(10868, 백준)

 기본적인 세그트리 문제이다. 주어진 구간에서의 최솟값을 찾는 문제이다. 

<소스 코드>

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

using namespace std;

int n, m;
int arr[100010], segtree[400010];

int init(int s, int e, int node)
{
	if (s == e) return segtree[node] = arr[s];
	int mid = (s + e) / 2;
	return segtree[node] = min(init(s, mid, node * 2), init(mid + 1, e, node * 2 + 1));
}

int segfind(int s, int e, int low, int high, int node)
{
	if (e < low || s > high) return 2e9;
	if (low <= s && e <= high) return segtree[node];
	int mid = (s + e) / 2;
	return min(segfind(s, mid, low, high, node * 2), segfind(mid + 1, e, low, high, node * 2 + 1));
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
	init(1, n, 1);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", segfind(1, n, x, y, 1));
	}
	return 0;
}