언제나 처음처럼

[문제 링크]

필자는 처음 풀 때 배열 크기를 arr[100000][3]으로 잡고 풀었는데, 메모리초과를 받았다.

다른 사람의 코드를 찾아봤는데 이유는 모르겠지만 배열 크기를 arr[100000][3] 으로 잡고도 정답을 받은 사람들이 많이 있었다.

분명 코드가 똑같은데 메모리초과를 받길래 계속 고민해봤지만 해답을 찾을 수 없었다. 아마도 입출력부분에서 메모리차이가 났던거 같다.

그러던중 N이 최대 100000이라고 해서 배열 크기를 100000으로 잡을 필요가 없다라는 힌트를 보고 정답을 받을 수 있었다. 문제 출제자의 출제 의도도 이쪽에 더 가깝다고 생각한다.

#include <iostream>
using namespace std;

int memoMin[3];
int memoMax[3];

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

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

	for (int i = 0; i < N; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (i == 0)
		{
			memoMin[0] = memoMax[0] = a;
			memoMin[1] = memoMax[1] = b;
			memoMin[2] = memoMax[2] = c;
		}
		else
		{
			int tempA, tempB, tempC;

			tempA = memoMin[0], tempB = memoMin[1], tempC = memoMin[2];

			memoMin[0] = min(tempA, tempB) + a;
			memoMin[1] = min(tempA, min(tempB, tempC)) + b;
			memoMin[2] = min(tempB, tempC) + c;

			tempA = memoMax[0], tempB = memoMax[1], tempC = memoMax[2];

			memoMax[0] = max(tempA, tempB) + a;
			memoMax[1] = max(tempA, max(tempB, tempC)) + b;
			memoMax[2] = max(tempB, tempC) + c;



		}
	}

	int minVal = min(memoMin[0], min(memoMin[1], memoMin[2]));
	int maxVal = max(memoMax[0], max(memoMax[1], memoMax[2]));

	cout << maxVal << ' ' << minVal << endl;

	return 0;
}

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

[문제 링크]

연속한 페이지끼리 합쳐야된다는 것을 모르고 풀어서 고생한 문제였다.

이 사실을 알고난 후로도 풀이법을 못떠올려서 다른 사람들의 블로그를 참고했다.

다양한 방법으로 풀이해보는 것을 더 연습해야겠다.

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

const int INF = 987654321;
int arr[501], sum[501], memo[501][501];

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

int Topdown(int start, int end)
{
	if (start >= end) return 0;
	if (start + 1 == end) return arr[start] + arr[end];

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

	ret = INF;

	for (int i = start; i <= end; i++)
		ret = min(ret, Topdown(start, i) + Topdown(i + 1, end) + sum[end] - sum[start - 1]);

	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		memset(sum, 0, sizeof(sum));

		int K;
		cin >> K;
		for (int i = 1; i <= K; i++)
		{
			cin >> arr[i];
			sum[i] = sum[i - 1] + arr[i];
		}

		cout << Topdown(1, K) << endl;
	}

	return 0;
}

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

[문제 링크]

top-down 방식으로 풀 경우 배열 (y,x)의 값이 1일 경우 가질 수 있는 가장 큰 정사각형 한 변의 길이는 →, ↓, ↘ 방향에 위치한 좌표에서 가질 수 있는 가장 큰 정사각형의 한 변의 길이 중 가장 작은값 + 1 이다. (y,x)의 값이 0일 경우는 정사각형이 만들어질 수 없기 때문에 변의 길이는 0 이다.

bottom-up 방식으로 풀 경우 채워나가는 방향이 반대이기 때문에 탐색 방향을 top-down과 반대로 하면 동일한 결과를 얻을 수 있다.

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

const int INF = 987654321;
int n, m, map[1001][1001], memo[1001][1001];

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

int Topdown(int hereY, int hereX)
{
	int dy[3] = { 0,1,1 };
	int dx[3] = { 1,0,1 };

	if (hereY > n || hereX > m) return 0;
	if (map[hereY][hereX] == 0) return 0;

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

	ret = 1;

	int res = INF;
	for (int i = 0; i < 3; i++)
	{
		int next = Topdown(hereY + dy[i], hereX + dx[i]);
		res = min(res, next);
	}

	return ret += res;
}

int Bottomup()
{
	int dy[3] = { 0,-1,-1 };
	int dx[3] = { -1,0,-1 };

	int res = 0;
	for(int i=1; i<=n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 0)
				memo[i][j] = 0;
			else
			{
				int last = INF;
				for (int k = 0; k < 3; k++)
					last = min(last, memo[i + dy[k]][j + dx[k]]);

				memo[i][j] = map[i][j] + last;
			}
			res = max(res, memo[i][j]);
		}

	return res * res;
}

int main(void)
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		string str;
		cin >> str;
		for (int j = 1; j <= m; j++)
			map[i][j] = str[j - 1] - '0';
	}
	
	// top-down
	int res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			res = max(res, Topdown(i, j));
	cout << res * res << endl;
	
	// bottom-up
	cout << Bottomup() << endl;

	return 0;
}

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

[문제 링크]

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)
{
	if (start == n) return 1;

	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];

	// top-down
	int res = 1;
	for (int i = 1; i <= n; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

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

	return 0;
}

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

[문제 링크]

k번째 방이 열려있거나 닫혀있는 경우는 k의 약수 갯수와 연관이 있다.

k의 약수 갯수가 홀수개라면 문이 열려있고, 짝수개라면 문이 닫혀있다는 것을 알 수 있다.

또한 n개의 방이 있을 때 n-1번째까지의 방은 방의 갯수가 늘어났다고하여 값이 변하는 것이 아닌 n-1개의 방이 있을 때 열려있는 문의 갯수와 동일하기 때문에 이를 메모이제이션하면 빠르게 정답을 구할 수 있다.

#include <iostream>
using namespace std;

int memo[101];

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

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

	int cnt = 0;
	for (int i = 1; i <= N; i++)
		if (N % i == 0) cnt++;

	return ret = Topdown(N - 1) + (cnt % 2);
}

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

	for (int i = 2; i <= N; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= i; j++)
			if (i % j == 0) cnt++;

		memo[i] = memo[i - 1] + (cnt % 2);
	}
    
	return memo[N];
}

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

	while (tc--)
	{
		int N;
		cin >> N;

		cout << Topdown(N) << endl;

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

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/104 점프 문제와 유사한 유형의 문제였다.

(y,x) 좌표에서 판다가 생존할 수 있는 일수는 항상 같기 때문에 이를 메모이제이션 해주면 중복 탐색을 최소화하게 되어 빠르게 정답을 구할 수 있다.

#include <iostream>
using namespace std;

int N, map[501][501], memo[501][501];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };

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

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

	ret = 1;

	for (int i = 0; i < 4; i++)
	{
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];
		if (nextY <= N && nextX <= N && map[startY][startX] < map[nextY][nextX])
			ret = max(ret, Topdown(nextY, nextX) + 1);
	}

	return ret;
}

int main(void)
{
	cin >> N;

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

	int res = 1;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			res = max(res, Topdown(i, j));

	cout << res << endl;

	return 0;
}

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

[문제 링크]

top-down으로 구현하다가 시간초과, 스택오버플로를 겪고 bottom-up으로 구현하였다.

이 문제를 N이 3일 때 까지 손으로 풀어보면 간단한 점화식을 발견할 수 있는데 점화식은 다음과 같다.

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

점화식은 간단하지만 필자는 위 점화식이 어떻게 참이 되는지 이해를 못하였기 때문에 위 점화식이 아닌 다른 방법으로 풀었다.

핵심은 옆에 칸에 사자를 배치했느냐 안했느냐에 따라서 경우의 수가 다르다는 것이다.

#include <iostream>
using namespace std;

const int MOD = 9901;
int memo[100001][2];

int Bottomup(int N)
{
	// [i][0] : 이전칸에 배치 했을 경우
	// [i][1] : 이전칸에 배치하지 않았을 경우
	memo[1][0] = 2;
	memo[1][1] = 3;

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

	return memo[N][1];
}

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

	cout << Bottomup(N) << endl;

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/102

내리막길 문제와 비슷한 유형의 문제였다.

(y,x)에서 (N,N)으로 가는 경우의 개수는 항상 같기 때문에 이를 메모이제이션 하면 중복을 최소화할 수 있다.

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

int N, arr[101][101];
long long memo[101][101];
int dy[2] = { 0, 1 }, dx[2] = { 1, 0 };

long long Topdown(int hereY, int hereX)
{
	if (hereY == N && hereX == N) return 1;
	if (arr[hereY][hereX] == 0) return 0;

	long long& ret = memo[hereY][hereX];
	if (ret != -1) return ret;

	ret = 0;

	int jump = arr[hereY][hereX];
	for (int i = 0; i < 2; i++)
	{
		int nextY = hereY + (dy[i] * jump);
		int nextX = hereX + (dx[i] * jump);

		if (nextY <= N && nextX <= N)
			ret += Topdown(nextY, nextX);
	}

	return ret;
}

long long Bottomup()
{
	memo[1][1] = 1;

	for(int i = 1; i<=N; i++)
		for (int j = 1; j <= N; j++)
		{
			if (arr[i][j] == 0)
				continue;

			if (i + arr[i][j] <= N)
				memo[i + arr[i][j]][j] += memo[i][j];

			if (j + arr[i][j] <= N)
				memo[i][j + arr[i][j]] += memo[i][j];
		}

	return memo[N][N];
}

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

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

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

	return 0;
}

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