언제나 처음처럼

[문제 링크]

변형된 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

[문제 링크]

간단한 dp 문제였다.

시작 숫자와 자릿수를 상태값으로 가져야하기 때문에 2차원 dp 배열이 필요하다.

문제 조건을 보면 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 인정해준다고 되어있기 때문에 이를 유의하여 점화식을 세워주면 된다.

top-down 방식의 경우 시작 숫자가 i 일 때 그 뒤에 나올 수 있는 숫자는 i보다 같거나 큰 숫자이다. 따라서 시작 숫자를 i로 하고 자릿수-1을 매개변수로 넘겨주어 재귀호출하는 방법으로 풀 수 있다. 첫번째 자리에 올 수 있는 숫자는 0~9이므로 이를 다 더해주면 된다. 기저사례로 자릿수가 0일 때 끝에 도달했으므로 1을 반환한다.

bottom-up 방식의 경우 자리수가 1이고 시작 숫자가 0~9 일 때 가질 수 있는 경우의 수를 미리 저장한 다음, 임의의 수 i부터 시작하고 자리수가 N인 경우의 수는 시작 숫자가 i~9이고 자리수가 N-1인 경우의 수의 합인 것을 이용하여 값을 갱신해가면 간단하게 원하는 결과를 얻을 수 있다. 

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

int memo[10][1001];

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

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

	for (int i = start; i < 10; i++)
		ret += Topdown(i, N - 1) % 10007;

	return ret % 10007;
}

int Bottomup(int N)
{
	memset(memo, 0, sizeof(memo));

	for (int i = 0; i < 10; i++)
		memo[i][1] = 10 - i;

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

	return memo[0][N] % 10007;
}

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

	// top-down
	cout << "top-down: " << Topdown(0,N) << endl;

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

	return 0;
}

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

[문제 링크]

이 문제는 점화식을 세우는 과정에서 자꾸 뇌정지가 와서 오래 걸린 문제였다.

top-down 방식의 경우 사이트가 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수는 서쪽의 N번째 사이트와 동쪽의 M번째 ~ N번째 사이트가 연결되는 경우의 수들의 합이다.

기저사례로 서쪽 사이트가 1개일 때, 동쪽 사이트 개수를 반환하고, 서쪽 사이트와 동쪽 사이트 개수가 같다면 1을 반환하였다.

bottom-up 방식의 경우 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수 = 서쪽의 N번째 사이트가 동쪽의 M번째 사이트와 연결되는 경우의 수 + 동쪽의 M-1번째 사이트와 연결되는 경우의 수이며, 이를 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int memo[31][31];

//* W = 서쪽, E = 동쪽 *//
int Topdown(int W, int E)
{
	if (W == 1) return E;
	if (W == E) return 1;

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

	for (int i = 1; i <= E; i++)
		ret += Topdown(W - 1, E - i);

	return ret;
}

int Bottomup(int W, int E)
{
	for (int i = 1; i <= E; i++)
		memo[1][i] = i;

	for(int i=2; i<=W; i++)
		for (int j = i; j <= E; j++)
			memo[i][j] = memo[i-1][j-1] + memo[i][j-1];

	return memo[W][E];
}

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

		// top-down
		cout << "top-down: " << Topdown(N, M) << endl;
		// bottom-up
		cout << "bottom-up: "<< Bottomup(N, M) << endl;
	}
	return 0;
}

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

[문제 링크]

길이가 2 x n 인 스티커에서 최대 점수를 구하는 방법은 다음과 같다.

max(d[0][n], d[1][n])

즉, 마지막줄에서 위에 칸을 떼어냈을 때 얻을 수 있는 최대값 vs 마지막줄에서 아래 칸을 떼어냈을 때 얻을 수 있는 최대값 중 더 큰값이 최대 점수가 된다.

n열에서 1행을 떼어냈을 때와 2행을 떼어냈을 때 얻을 수 있는 최대값을 구하는 점화식은 다음과 같이 나타낼 수 있다.

dp(0, n) = max(dp(1, n-1) + score[0][n], dp(1, n-2) + score[0][n])

dp(1, n) = max(dp(0, n-1) + score[1][n], dp(0, n-2) + score[1][n])

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

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

int P[2][100000], memo[2][100000];

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

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

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

	if (y == 0) return ret = max(Topdown(1, x - 1), Topdown(1, x - 2)) + P[0][x];
	if (y == 1) return ret = max(Topdown(0, x - 1), Topdown(0, x - 2)) + P[1][x];
}

int Bottomup(int n)
{
	memo[0][0] = P[0][0];
	memo[1][0] = P[1][0];
	memo[0][1] = memo[1][0] + P[0][1];
	memo[1][1] = memo[0][0] + P[1][1];

	for (int i = 2; i < n; i++)
	{
		memo[0][i] = max(memo[1][i - 1], memo[1][i - 2]) + P[0][i];
		memo[1][i] = max(memo[0][i - 1], memo[0][i - 2]) + P[1][i];
	}

	return max(memo[0][n - 1], memo[1][n - 1]);
}
int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < n; j++)
				cin >> P[i][j];

		// top-down
		cout << "top-down: " << max(Topdown(0, n - 1), Topdown(1, n - 1)) << endl;

		// bottom-up
		cout << "bottom-up: " << Bottomup(n) << endl;
	}

	return 0;
}

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

[문제 링크]

N X M 크기의 초콜릿을 가장 적게 자르는 횟수를 구하는 공식은 (N * M - 1)이다. 이 공식을 통해서도 쉽게 정답을 구할 수 있다.

필자는 dp를 연습하기 위해 공식을 사용하지 않고 점화식을 세워서 풀었다.

N X M 크기의 초콜릿을 가장 적게 자르는 횟수는 (y축을 1~N/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1)과 (x축을 1~M/2개 잘랐을 때 나오는 두개의 조각을 가장 적게 자르는 횟수 + 1) 중 최솟값이다.

따라서 점화식은 다음과 같이 나타낼 수 있다.

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

dp[N][M] = max(dp[N][M], dp(i, M) + dp(N-i, M) + 1)

for(j = 1; j <= M/2; j++)

dp[N][M] = max(dp[N][M], dp(N, i) + dp(N, M-i) + 1) 

N X M 과 M X N 초콜릿은 서로 모양만 다를뿐 같은 초콜릿이기 때문에 중복을 최소화하여 효율성을 높였다.

#include <iostream>
using namespace std;

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

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

int Topdown(int y, int x)
{
	if (y == 1 || x == 1) return y == 1 ? x - 1 : y - 1;

	int& retA = memo[y][x];
	int& retB = memo[x][y];

	if (retA != 0 || retB != 0) return retA;

	int ret = INF;

	for (int i = 1; i <= y / 2; i++) // 가로로 자르기
		ret = min(ret, Topdown(i, x) + Topdown(y - i, x) + 1);

	for (int i = 1; i <= x / 2; i++) // 세로로 자르기
		ret = min(ret, Topdown(y, i) + Topdown(y, x - i) + 1);

	return retA = retB = ret;
}

int main(void)
{
	int y, x;
	cin >> y >> x;

	// top-down
	cout << Topdown(y, x) << endl;

	return 0;
}

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

[문제 링크]

간단한 dp문제였다.

Top-down 방식으로 푸는 경우, N개의 카드를 가장 비싸게 구입하는 금액은 카드를 i개 묶음을 구입하는 금액 + N-i개의 카드를 가장 비싸게 구입하는 금액이다. 여기서 i를 1~N까지 반복하여 그 중 최대값을 구해주면 된다.

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

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

dp(N) = max(dp[N], dp[N-i] + P[i]);

Bottom-up 방식으로 푸는 경우, 이중 for문을 통해 구현할 수 있으며 점화식은 Top-down 방식과 동일하다.

#include <iostream>
using namespace std;

int P[1001], memo[1001];

inline int max(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;

	for (int i = 1; i <= N; i++)
		ret = max(ret, Topdown(N - i) + P[i]);

	return ret;
}

int Bottomup(int N)
{
	// memo[0] = 0 으로 초기화 해줘야 하지만 전역변수는 기본값이 0이므로 생략
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i; j++)
			memo[i] = max(memo[i], memo[i - j] + P[j]);

	return memo[N];
}

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

	for (int i = 1; i <= N; i++)
		cin >> P[i];

	// top-down
	cout << "Top-down: " << Topdown(N) << endl;

	// Bottom-up
	cout << "Bottom-up: "<< Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

지난번에 완전탐색으로 한번 풀었던 문제였는데 이번에 동적 계획법을 사용하여 다시 풀게되었다.

아래에서 위로 탐색하는 알고리즘은 금방 생각해냈지만, 위에서 아래로 탐색하여 정답을 얻어내는 알고리즘을 생각하다가 이틀이나 날려먹었다.....

일단은 아래에서 위로 재귀호출을 통해 탐색하는 방식으로 문제를 해결하였다.

이 문제의 핵심은 해당 일에 상담을 했을 때 얻는 최대이익과 상담을 하지 않았을 때 얻는 최대이익 중 더 큰 값을 선택한다는 것에 있다.

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

dp(N) = max(dp(N+1), dp(N+T[N]) + P[N]);

위 점화식을 알고리즘으로 구현하면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

const int INF = 987654321;
int N, T[16], P[16], memo[16];
inline int max(int a, int b) { return a > b ? a : b; }

int brute(int start, int pay)
{
	int ret = pay;
	for (int i = start; i < N; i++)
	{
		int next = i + T[i];
		if (next > N) continue;
		ret = max(ret, brute(next, pay + P[i]));
	}
	return ret;
}

int Topdown(int start)
{
	if (start >= N) return start == N ? 0 : -INF;

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

	return ret = max(Topdown(start + 1), Topdown(start + T[start]) + P[start]);
}

int main(void)
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> T[i] >> P[i];

	// brute-force
	cout << brute(0, 0) << endl;

	// top-down
	cout << Topdown(0) << endl;

	return 0;
}

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