언제나 처음처럼

[문제 링크]

간단한 DP 문제였다.

자신의 차례에서 1개나 3개를 가져갔을 때 상대방이 승리하는지 여부는 가져간 개수에서 상대방이 1개나 3개를 가져갔을 때 자신이 승리하는지 여부에 결정된다. 그리고 이것을 계속 반복하다가 결국 기저사례 (N=1, N=2, N=3)에 도달하게 되면 최종적으로 승리와 패배가 결정되게 된다. 점화식은 다음과 같다.

Dp(N) = !(DP(N-1) || DP(N-3))

참고로 이 문제는 베스킨라빈스31 게임처럼 규칙 상 무조건 승리하는 필승법이 있다. 짝수개가 남도록 가져가면 결국 상대방이 패배한다. 즉 N이 홀수면 상근이가 이기고, 짝수면 창영이 이기게 된다.

#include <iostream>
using namespace std;

bool memo[1001] = {false,};
bool visited[1001] = {false,};

bool Topdown(int remain)
{
    if(remain == 1 || remain == 3)
    {
        return true;
    }   
    else if(remain == 2)
    {
        return false;
    }
    
    if(visited[remain]) 
    {
        return memo[remain];        
    }
    
    visited[remain] = true;
    
    return memo[remain] = !(Topdown(remain-1) || Topdown(remain-3));
}

bool Bottomup(int remain)
{
    memo[1] = true;
    memo[2] = false;
    memo[3] = true;
    
    for(int i = 4; i<=remain; ++i)
    {
        memo[i] = !(memo[i-1] || memo[i-3]);
    }
    
    return memo[remain];
}

int main(void)
{
    int N;
    cin >> N;
    
    if(Topdown(N))
    {
        cout << "SK";
    }   
    else 
    {
        cout << "CY";
    }
    
    return 0;
}

[문제 링크]

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

문제에 결과를 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