백준 1344번 축구

문제 링크입니다: https://www.acmicpc.net/problem/1344

 

문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 구간, A팀 득점 수, B팀 득점 수임을 유추할 수 있습니다.

따라서 세 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.

 

	#include <iostream>
	#include <cstring>
	using namespace std;
	const int MAX = 18 + 1;
	double A, B;
	int minFactor[MAX];
	double cache[MAX][MAX][MAX];
	void eratosthenes()
	{
	minFactor[0] = minFactor[1] = -1;
	for (int i = 2; i < MAX; i++)
	{
	minFactor[i] = i;
	}
	for (int i = 2; i * i < MAX; i++)
	{
	if (minFactor[i] != i)
	{
	continue;
	}
	for (int j = i * i; j < MAX; j += i)
	{
	if (minFactor[j] == j)
	{
	minFactor[j] = i;
	}
	}
	}
	}
	double func(int idx, int a, int b)
	{
	if (idx == 18)
	{
	if (minFactor[a] == a
	|| minFactor[b] == b)
	{
	return 1.0;
	}
	return 0.0;
	}
	double& result = cache[idx][a][b];
	if (result > -0.5)
	{
	return result;
	}
	result = 0.0;
	result += A * B * func(idx + 1, a + 1, b + 1);
	result += A * (1 - B) * func(idx + 1, a + 1, b);
	result += (1 - A) * B * func(idx + 1, a, b + 1);
	result += (1 - A) * (1 - B) * func(idx + 1, a, b);
	return result;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> A >> B;
	A /= 100;
	B /= 100;
	eratosthenes();
	memset(cache, -1, sizeof(cache));
	printf("%.6lf\n", func(0, 0, 0));
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~