언제나 처음처럼

[문제 링크]

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

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

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

[문제 링크]

변형된 LIS문제였다.

필자는 길이가 i인 수열에서 i번째 원소를 반드시 포함할 때 갖는 최대값을 memo[i]에 저장하였다.

수열의 길이 N을 입력받았다면 1~N까지 위 작업을 진행한 다음 memo[1]~memo[N]에서 가장 큰 값을 찾아주면 원하는 정답을 얻을 수 있다.

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

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

int Topdown(int N)
{
	if (N == 0) return arr[N];

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

	for (int i = 0; i < N; i++)
		if (arr[i] < arr[N])
			ret = max(ret, Topdown(i) + arr[N]);
	
	return ret;
}

int Bottomup(int N)
{
	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		memo[i] = arr[i];
		for (int j = 0; j < i; j++)
			if (arr[i] > arr[j])
				memo[i] = max(memo[i], memo[j] + arr[i]);
		
		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	//top-down
	int res = 0;
	for(int i=0; i<N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

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

	return 0;
}

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

[문제 링크]

간단한 dp 문제였다.

자연수 N을 제곱수의 합으로 나타낼 때 최소항의 개수를 찾는 방법은 min(1 + [N - (제곱한 값이 N보다 작거나 같은 수들의 제곱수)]의 항의 개수) 이다.

예를 들어 N = 10 일 때 최소 항의 개수는 dp[10] = min( 1 + dp[10-1], 1 + dp[10-4], 1 + dp[10-9] ) 로 나타낼 수 있다.

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

for(i = 1; i<=N; i++)

if(i*i <= N) dp[N] = min(dp[N], 1 + dp[N-i*i])

#include <iostream>
using namespace std;

const int INF = 987654321;
int memo[100001];

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

int Topdown(int N)
{
	if (N == 0) return 0;

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

	ret = INF;

	for (int i = 1; i <= N; i++)
	{
		if (i*i > N) break;
		ret = min(ret, 1 + Topdown(N - i * i));
	}

	return ret;
}

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

	for (int i = 2; i <= N; i++)
	{
		memo[i] = INF;
		for (int j = 1; j <= N; j++)
		{
			if (j*j > i) break;
			memo[i] = min(memo[i], 1 + memo[i - j * j]);
		}
	}

	return memo[N];
}
int main(void)
{
	int N;
	cin >> N;

	cout << "top-down: " << Topdown(N) << endl;
	cout << "bottom-up: " << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

top-down 방식으로 풀어보려다 너무 많은 시간을 허비한 문제였다.

동전의 순서만 다른 경우를 가려내기 위해선 2차원 dp 배열을 선언해야 하는데 dp[101][10001] 으로 선언하게 되면 메모리가 4mb를 넘게되어 메모리 초과가 발생하게 된다.

bottom-up 방식으로 풀었더니 코드도 훨씬 간결하고 쉽게 풀렸다. 

틀에 박힌 사고를 개선해야 한다는 것을 다시한번 느끼게 된 문제였다.

#include <iostream>
using namespace std;

int n, k, pay[101], memo[10001];

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

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if(j - pay[i] >= 0)
				memo[j] += memo[j - pay[i]];

	return memo[k];
}

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

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

	cout << Bottomup(k) << endl;

	return 0;
}

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