언제나 처음처럼

[문제 링크]

(비대칭 타일수 = 전체 타일수 - 대칭 타일수) 라는 것을 알 수 있다.

n이 홀수라면 가운데 타일이 놓이는 경우가 1개 밖에 없지만, 짝수라면 가운데 타일이 놓이는 경우가 2개 존재한다.

따라서 n에 대한 전체 타일수를 구한 다음,

n이 홀수라면 전체 타일수에 (n / 2)에 대한 전체 타일수를 빼주고,

n이 짝수라면 전체 타일수에 (n / 2)에 대한 전체 타일수와 (n / 2 -1)에 대한 전체 타일수를 빼준다.

위 과정을 통해 결과적으로 양쪽 타일이 대칭인 경우를 제거할 수 있다.

 1,000,000,007 을 나눠주기 전에 먼저 한번 더해줘야 한다는 것을 생각하지 못하여 책을 보고 이해하게 되었다.

(만약 1,000,000,008과 1,000,000,006이 있을 때 전자는 나머지 결과 1이라는 값을 가지고, 후자는 1,000,000,006 값을 가지게 되는데 전자와 후자의 차는 2가 정상이지만, 나머지 연산을 거치면서 -1,000,000,005 값을 가지게 되어 오류가 출력될 수 있기 때문. -1,000,000,005에 1,000,000,007을 더해주게 되면 값이 2로 바뀜)

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

const int MOD = 1000000007;
int memo[101];

int tilingCount(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 2;

	int& ret = memo[n];
	if (ret != -1) return ret;
	return ret = (tilingCount(n - 1) + tilingCount(n - 2)) % MOD;
}
int Solution(int n)
{
	if (n % 2 == 1) return (tilingCount(n) - tilingCount(n / 2) + MOD) % MOD;

	int ret = tilingCount(n);
	ret = (ret - tilingCount(n / 2) + MOD) % MOD;
	ret = (ret - tilingCount(n / 2 - 1) + MOD) % MOD;
	return ret;
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		int n;
		cin >> n;
		if (n == 2) 
			cout << "0" << endl;
		else
			cout << Solution(n)<< endl;
	}
	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략 책에 나와있는 알고리즘과 동일하게 구현하였다.

제대로 구현한 것이 분명한데 자꾸 쌩뚱맞은 결과가 출력되어서 골머리를 앓았다.

double형 2차원 배열을 memset()함수를 통해 -1로 초기화했다는 것이 오답의 원인이었다.

이중 for문으로 memo[1001][2001] 배열을 -1로 초기화하여 문제를 해결하였다.

#include <cstdio>
using namespace std;

double memo[1001][2001];
int n, m;

double Solution(int days, int clime)
{
	if (days == m) return clime >= n ? 1 : 0;

	double& ret = memo[days][clime];
	if (ret != -1) return ret;

	return ret = (0.25 * Solution(days + 1, clime + 1)) + (0.75 * Solution(days + 1, clime + 2));
}
int main(void)
{
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		for (int i = 0; i < 1001; i++)
			for (int j = 0; j < 2001; j++)
				memo[i][j] = -1;

		scanf("%d %d", &n, &m);
		printf("%.10f\n", Solution(0, 0));
	}

	return 0;
}

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

[문제 링크]

알고리즘은 다음과 같다.

먼저, tri[Y][X] 좌표에서 시작했을 때 최대값을 memo[Y][X]배열에 메모라이징하는 함수를 수행한다.

그 다음 최대 경로의 개수를 카운팅하는 함수를 수행한다. memo[Y][X]에는 좌표가 가지는 최대값이 저장되므로 memo[0][0]을 시작으로 갈 수 있는 좌표인 memo[Y+1][X] 와 memo[Y+1][X+1] 을 비교하여

값이 같을 경우 두 개의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수의 합을 cntmemo[Y][X]에 저장하고,

값이 다를 경우 더 큰 쪽의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수를  cntmemo[Y][X]에 저장한다.

기저사례로 Y == n-1 일 때, 즉 맨 아래에 도달했을 때 1을 리턴하여 최대 경로 개수를 카운팅해주면 원하는 결과를 얻을 수 있다.

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

int n, tri[101][101], memo[101][101], cntmemo[101][101];

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

int Solution(int startY, int startX)
{
	if (startY == n) return 0;

	int& ret = memo[startY][startX];
	if (ret != -1) return ret;
	
	int val = tri[startY][startX];
	return ret = max(val + Solution(startY + 1, startX), val + Solution(startY + 1, startX + 1));
}

int CountPath(int startY, int startX)
{
	if (startY == n-1) return 1;

	int& ret = cntmemo[startY][startX];
	if (ret != -1) return ret;

	ret = 0;
	if (memo[startY + 1][startX] > memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX);
	else if (memo[startY + 1][startX] < memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX + 1);
	else
		return ret += CountPath(startY + 1, startX) + CountPath(startY + 1, startX + 1);
}

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

		Solution(0,0);
		cout << CountPath(0, 0) << endl;
	}

	return 0;
}

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

[문제 링크]

비교 연산자가 많고 복잡해서 잔실수들을 고치느라 시간이 오래걸린 문제였다.

세 자리에서 다섯 자리까지로 끊어서 읽기 때문에 나올 수 있는 경우의 수는 한정되어 있다.

세 자리부터 다섯 자리까지 끊어서 읽을 수 있는 모든 경우의 수에 대하여 나올 수 있는 난이도의 합이 최소가 되는 값을 찾아주면 된다.

마지막에 남는 자리수가 2개 이하라면 잘못 끊어서 읽은 것이기 때문에 불가능(INF)값을 리턴한다.

추가로 PI[start]가 가질 수 있는 최소 난이도는 항상 같으므로 메모이제이션을 적용하면 제한시간 안에 문제를 풀 수 있다.

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

const int INF = 987654321;
int memo[10001], digit;
string PI;

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

int Solution(int start)
{
	if (start == digit) return 0;

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

	ret = INF;

	if (start + 2 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';

		if (a == b && b == c)
			ret = min(ret, Solution(start + 3) + 1);

		else if ( (b == a + 1 && c == b + 1) || 
				  (b == a - 1 && c == b - 1) )
			ret = min(ret, Solution(start + 3) + 2);

		else if (a == c && a != b)
			ret = min(ret, Solution(start + 3) + 4);

		else if (a - b == b - c)
			ret = min(ret, Solution(start + 3) + 5);

		else
			ret = min(ret, Solution(start + 3) + 10);
	}

	if (start + 3 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';

		if (a == b && b == c && c == d)
			ret = min(ret, Solution(start + 4) + 1);

		else if ( (b == a + 1 && c == b + 1 && d == c + 1) || 
				  (b == a - 1 && c == b - 1 && d == c - 1) )
			ret = min(ret, Solution(start + 4) + 2);

		else if (a == c && b == d)
			ret = min(ret, Solution(start + 4) + 4);

		else if (a - b == b - c && b - c == c - d)
			ret = min(ret, Solution(start + 4) + 5);

		else
			ret = min(ret, Solution(start + 4) + 10);
	}

	if (start + 4 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';
		int e = PI[start + 4] - '0';

		if (a == b && b == c && c == d && d == e)
			ret = min(ret, Solution(start + 5) + 1);

		else if ((b == a + 1 && c == b + 1 && d == c + 1 && e == d + 1) || 
				 (b == a - 1 && c == b - 1 && d == c - 1 && e == d - 1))
			ret = min(ret, Solution(start + 5) + 2);

		else if (a == c && a == e && b == d)
			ret = min(ret, Solution(start + 5) + 4);

		else if (a - b == b - c && b - c == c - d && c - d == d - e)
			ret = min(ret, Solution(start + 5) + 5);

		else
			ret = min(ret, Solution(start + 5) + 10);
	}

	return ret;
}
int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> PI;
		digit = PI.size();

		cout << Solution(0) << endl;
	}
	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

핵심은 두 개의 배열 A, B에서 현재 숫자보다 더 큰 수를 고르는 경우를 모두 해보면서 startA, startB를 초기값으로 시작할 때 가질 수 있는 최대 길이는 일정하기 때문에 이를 메모라이징하여 중복 탐색을 최소화 하는 것이라 생각한다.

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

int n, m, A[101], B[101], memo[101][101];
const long long MIN = numeric_limits<long long>::min();

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

	ret = 2;
	long long a = (startA == -1 ? MIN : A[startA]);
	long long b = (startB == -1 ? MIN : B[startB]);
	long long maxValue = max(a, b);

	for (int i = startA + 1; i < n; i++)
		if (maxValue < A[i])
			ret = max(ret, Solution(i, startB) + 1);
	for (int i = startB + 1; i < m; i++)
		if (maxValue < B[i])
			ret = max(ret, Solution(startA, i) + 1);

	return ret;
}
int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> A[i];
		for (int i = 0; i < m; i++)
			cin >> B[i];

		cout << Solution(-1, -1) - 2 << endl;
	}
	return 0;
}

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

[문제 링크]

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

핵심은 아래에서 위로 탐색하면서 최대가 되는 값을 선택하는 것이라고 생각한다.

(y,x) 위치에서 아래칸을 선택할 수 있는 경우는 (y+1, x), (y+1, x+1) 두 가지 경우밖에 존재하지 않기 때문에 두 가지 경우 중 가질 수 있는 최대값이 더 큰 쪽을 선택해야 한다.

아래칸이 가질 수 있는 최대값을 알아야 하기 때문에, 맨 아래에서 위로 탐색하는 것이다.

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

int n, triangle[101][101], memo[101][101];

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

int Solution(int y, int x)
{
	if (y == n - 1) return triangle[y][x];

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

	return ret = max(Solution(y + 1, x), Solution(y + 1, x + 1)) + triangle[y][x];
}

int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= i; j++)
				cin >> triangle[i][j];

		cout << Solution(0, 0) << endl;
	}
}

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

[문제 링크]

알고리즘 문제해결전략 책에 나와있는 알고리즘과 동일하게 구현하였다.

문제에 결과를 ASCII코드 순서로 출력하라는 조건이 있기 때문에 vector 배열에 조건을 만족하는 파일명을 저장한 다음, 오름차순 정렬 후 출력해주었다.

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

int memo[101][101];
string wild, file;

bool Solution(int w, int f)
{
	int& ret = memo[w][f];

	if (ret != -1) return ret;

	while (w < wild.size() && f < file.size() && (wild[w] == '?' || wild[w] == file[f]))
	{
		w++, f++;
	}
	if (w == wild.size() && f == file.size())
		return ret = 1;

	if (wild[w] == '*')
		if (Solution(w + 1, f) || (f < file.size() && Solution(w, f + 1)))
			return ret = 1;

	return ret = 0;
}
int main(void)
{
	int testcase;
	cin >> testcase;

	while (testcase--)
	{
		int num;
		cin >> wild >> num;

		vector<string> result;
		for (int i = 0; i < num; i++)
		{
			cin >> file;
			memset(memo, -1, sizeof(memo));

			if(Solution(0, 0))
				result.push_back(file);
		}
		sort(result.begin(), result.end());

		for (int i = 0; i < result.size(); i++)
			cout << result[i] << endl;
		
		result.clear();
	}
	return 0;
}

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

[문제 링크]

책보고 정석으로 공부하면서 스스로 풀게된 첫번째 동적계획법 유형의 문제이다.

Solution(y, x)는 입력이 같을 경우 항상 같은 값을 반환하는 참조적 투명 함수이기 때문에, 메모이제이션 기법을 적용할 수 있다.

최대 크기가 100X100인 2차원 배열 memo[100][100] 를 선언하고 -1로 초기화하여, memo[y][x]가 -1이라면 처음 방문하는 지점이므로 성공 여부를 탐색하고, 성공 여부를 저장한다. -1이 아니라면 이미 탐색했던 지점이므로 memo[y][x]값을 바로 리턴해준다.

기저사례로 배열의 범위를 벗어날 경우 false, 현재 좌표가 (N-1, N-1) 이라면 끝에 도달한 것이므로 true를 반환해주도록 구현하였다.

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

int N, board[100][100], memo[100][100];

bool Solution(int startY,int startX)
{
	if (startY >= N || startX >= N) return false; // 기저사례. 범위 벗어나면 false

	if (startY == N - 1 && startX == N - 1) return true; // 기저사례. 끝에 도달했다면 true

	int& ret = memo[startY][startX];

	if (ret != -1) return ret; // 메모이제이션. 이미 해당 좌표에 대해 경로탐색을 해봤다면 저장한 성공여부 반환

	return ret = Solution(startY + board[startY][startX], startX) || Solution(startY, startX + board[startY][startX]);
}

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

	while (testcase--)
	{
		cin >> N;
		memset(memo, -1, sizeof(board));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> board[i][j];

		if (Solution(0, 0))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

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