언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/80 LIS와 같은 유형의 문제였다.

#include <iostream>
using namespace std;

int N, arr[1001], memo[1001];

int max(int a, int b) { return a > b ? a : b; }

int Topdown(int start)
{
	int& ret = memo[start];
	if (ret != 0) return ret;

	ret = 1;
	for (int i = start + 1; i <= N; i++)
		if (arr[start] > arr[i])
			ret = max(ret, Topdown(i) + 1);

	return ret;
}

int Bottomup()
{
	int res = 1;
	for (int i = 1; i <= N; i++)
	{
		memo[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[i] < arr[j])
				memo[i] = max(memo[i], memo[j] + 1);
		res = max(res, memo[i]);
	}

	return res;
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	int res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	cout << Bottomup() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 87 day

[문제 링크]

https://onlytrying.tistory.com/81 타일 문제와 비슷한 유형의 문제라고 생각한다.

N == 1일 때 만들 수 있는 타일은 1 한가지 존재하고,

N == 2일 때 만들 수 있는 타일은 00, 11 두가지 존재한다.

N == 3일 때 만들 수 있는 타일은 N==1일 때 만들 수 있는 타일 뒤에 N==2일 때 만들 수 있는 타일을 붙인 모양(100, 111)과 새롭게 만들 수 있는 001이 추가되어 세가지 존재하게 된다.

이를 통해 앞서 많이 풀어봤던 타일채우기 문제들과 동일한 유형의 문제임을 알 수 있다.

따라서 점화식은 다음과 같다.

dp(N) = dp(N-2) * 2 + dp(N-3)

#include <iostream>
using namespace std;

const int MOD = 15746;
int memo[1000001];

int Topdown(int N)
{
	if (N == 1) return 1;
	if (N == 2) return 2;
	if (N == 3) return 3;

	int& ret = memo[N];
	if (ret != 0) return ret;

	return ret = (Topdown(N - 2) * 2 + Topdown(N - 3)) % MOD;
}

int Bottomup(int N)
{
	memo[1] = 1;
	memo[2] = 2;
	memo[3] = 3;

	for (int i = 4; i <= N; i++)
		memo[i] = (memo[i - 2] * 2 + memo[i - 3]) % MOD;

	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	cout << Topdown(N) << endl;

	cout << Bottomup(N) << endl;
	
	return 0;
}

알고리즘 200일 프로젝트 - 87 day

[문제 링크]

이항 계수를 구하는 점화식을 이용하여 쉽게 풀 수 있는 문제였다.

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 10007;
int memo[1001][1001];

int Topdown(int N, int K)
{
	if (K == 1) return N;
	if (K == 0 || K == N) return 1;

	int& ret = memo[N][K];
	if (ret != -1) return ret;

	return ret = ((Topdown(N - 1, K - 1) % MOD) + (Topdown(N - 1, K) % MOD)) % MOD;
}

int Bottomup(int N, int K)
{
	memo[1][0] = memo[1][1] = 1;

	for (int i = 2; i <= N; i++)
		for (int j = 0; j <= i; j++)
			memo[i][j] = ((memo[i - 1][j] % MOD) + (memo[i - 1][j - 1] % MOD)) % MOD;

	return memo[N][K];
}

int main(void)
{
	int N, K;
	cin >> N >> K;

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, K) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 86 day

[문제 링크]

난이도 있는 타일채우기 문제였던거 같다.

점화식을 이해한다면 쉬운 문제지만 이해하기까지가 조금 까다롭다.

3XN 타일을 2칸짜리 블록(2X1, 1X2)으로 채워야하기 때문에 N이 홀수이면 채울 수 있는 경우의 수는 0이다.

또한 그림으로 3X4, 3X6 타일을 직접 그려보면 N이 2 증가할 때마다 새로운 모양으로 채우는 경우가 2개 생긴다.

따라서 점화식은 dp(N) = dp(N-2) * dp(2) + sum(dp(N-4 ~ N-(N-2)) * 2) + 2 로 나타낼 수 있다.

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <cstring>
using namespace std;

int memo[31];

int Topdown(int N)
{
	if (N % 2 == 1) return 0;
	if (N == 0) return 0;
	if (N == 2) return 3;
	

	int& ret = memo[N];
	if (ret != -1) return ret;

	ret = Topdown(N - 2) * 3;
	N -= 2;

	while (N > 0)
	{
		ret += Topdown(N - 2) * 2;
		N -= 2;
	}

	return ret += 2;
}

int Bottomup(int N)
{
	memo[0] = 1;

	for (int i = 2; i <= N; i += 2)
	{
		memo[i] = memo[i - 2] * 3;

		for (int j = 4; j <= i; j += 2)
			memo[i] += memo[i - j] * 2;
	}

	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day

[문제 링크]

https://onlytrying.tistory.com/89 동전 1의 변형 문제였다.

입력받은 동전의 가치를 배열 coin[n]에 저장할 때, k원을 만드는 동전의 최소 개수는 i = 1~n까지 k-coin[i]원을 만드는 최소 개수가 가장 작은 개수 + 1이다.

k원을 만들지 못하는 경우 -1을 출력해줘야 하기 때문에 top-down에서는 기저사례로 k가 0보다 작을 때 무한대(INF)를 반환하도록 하였고, bottom-up에서는 초기값을 무한대(INF)로 초기화하였다.

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 987654321;
int n, k, coin[101], memoTop[101][10000], memoBot[10000];

inline int min(int a, int b) { return a < b ? a : b; }

int Topdown(int start, int k)
{
	if (k <= 0) return k == 0 ? 0 : INF;

	int& ret = memoTop[start][k];
	if (ret != -1) return ret;

	ret = INF;
	for (int i = start; i <= n; i++)
		ret = min(ret, Topdown(i, k - coin[i]) + 1);

	return ret;
}

int Bottomup(int k)
{
	for (int i = 1; i <= k; i++)
	{
		memoBot[i] = INF;
		for (int j = 1; j <= n; j++)
			if (i - coin[j] >= 0)
				memoBot[i] = min(memoBot[i], memoBot[i - coin[j]] + 1);
	}
	
	return memoBot[k] == INF ? -1 : memoBot[k];
}

int main(void)
{
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> coin[i];

	// top-down
	memset(memoTop, -1, sizeof(memoTop));
	int res = Topdown(1, k);
	if (res == INF)
		cout << -1 << endl;
	else
		cout << res << endl;

	// bottom-up
	cout << Bottomup(k) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day

[문제 링크]

간단한 dp문제였다.

이동할수 있는 방향이 (y+1, x), (y, x+1), (y+1, x+1) 세가지 존재하기 때문에 (N, M)까지 이동할 때 얻을 수 있는 사탕 개수의 최댓값은 (N, M) 이전에 위치할 수 있는 좌표들 중 최댓값을 선택하도록 구현하면 원하는 결과를 얻을 수 있다.

추가) 좌표에 존재하는 사탕개수가 0 이상이기 때문에 대각선으로 이동하는 것보다 왼쪽 또는 아래로 이동하는 것이 항상 이득이다. 따라서 대각선으로 이동하는 (y+1, x+1) 의 경우는 고려하지 않아도 된다.

#include <iostream>
#include <cstring>
using namespace std;

int arr[1001][1001], memo[1001][1001];

inline int max(int a, int b) { return a > b ? a : b; }

int Topdown(int y, int x)
{
	if (y == 0 || x == 0)
		return 0;

	int& ret = memo[y][x];
	if (ret != -1) return ret;

	return ret = max(Topdown(y - 1, x), max(Topdown(y, x - 1), Topdown(y - 1, x - 1))) + arr[y][x];
}

int Bottomup(int N, int M)
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			memo[i][j] = max(memo[i - 1][j], max(memo[i][j - 1], memo[i - 1][j - 1])) + arr[i][j];

	return memo[N][M];
}

int main(void)
{
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> arr[i][j];

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N, M) << endl;
	
	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N, M) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day

[문제 링크]

필자는 1행 1열에서 1행 M열까지 숫자를 입력받는다고 했을 때, 1행 i열에 1열부터 i열까지의 합을 메모이제이션하였다.

미리 배열의 합을 계산한 이유는 1행 i열부터 1행 j열까지 배열의 합을 memo[1][j] - memo[1][i-1] 식으로 간단히 구할 수 있기 때문이다.

위 식을 이용하여 각 행마다 배열의 합을 구하고 결과값에 누적시켜주면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int memo[301][301];

int Solution(int i, int j, int x, int y)
{
	int ret = 0;
	for (int col = i; col <= x; col++)
		ret += memo[col][y] - memo[col][j-1];

	return ret;
}

int main(void)
{
	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int num, sum = 0;
		for (int j = 1; j <= M; j++)
		{
			cin >> num;
			sum += num;
			memo[i][j] = sum;
		}
	}

	int K;
	cin >> K;
	while (K--)
	{
		int i, j, x, y;
		cin >> i >> j >> x >> y;
		cout << Solution(i, j, x, y) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 82 day

[문제 링크]

문자열 A, B의 시작 지점에 따라 LCS는 각각 다르기 때문에 2차원 dp배열을 선언하였다.

문자열 A, B 모두 첫번째 원소에서 시작할 때 가지는 최대 길이는 A의 첫번째 문자와 같은 문자가 B에 존재하는 경우

A의 첫번째 문자를 LCS에 포함시킨 다음 A의 두번째 원소, B에서 A의 첫번째 문자와 일치하는 원소의 다음 위치에서 시작할 때 가지는 최대 길이 vs  첫번째 원소를 LCS에 포함시키지 않고 A의 두번째  원소, B의 첫번째 원소에서 시작할 때 가지는 최대 길이 중 더 큰 값이 정답이 된다.

만약 A의 첫번째 문자와 같은 문자가 B에 존재하지 않을 경우 LCS에 포함시킬 수 없기 때문에 최대 길이는 A의 두번째 원소, B의 첫번째 원소를 시작으로 할 때 최대 길이가 정답이 된다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int memo[1000][1000];
string strA, strB;

int max(int a, int b) { return a > b ? a : b; }

int Topdown(int startA, int startB)
{
	if (startA == strA.length() || startB == strB.length())
		return 0;

	int& ret = memo[startA][startB];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = startB; i < strB.length(); i++)
		if (strA[startA] == strB[i])
			return ret = max(Topdown(startA+1, startB), Topdown(startA+1, i + 1) + 1);

	return ret = Topdown(startA+1, startB);
}

int main(void)
{
	memset(memo, -1, sizeof(memo));

	cin >> strA >> strB;

	cout << Topdown(0,0) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 80 day