[C++] 백준(BOJ) - 1344 : 축구
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
홍준이는 축구 경기를 보고 있다. 그러다가 홍준이는 역시 두 팀 중 적어도 한 팀이 골을 소수로 득점할 확률이 궁금해 졌다. 축구 경기는 90분동안 이루어지고, 분석을 쉽게하기 위해서 경기를 5분 간격으로 나눴다. 처음 간격은 처음 5분이고, 두 번째 간격은 그 다음 5분, 그리고 이런식으로 나눈다. 경기가 진행되는 동안 각 간격에서 A팀이 득점할 확률과 B팀이 득점할 확률이 주어진다. 그리고, 각 간격에서 두 팀은 각각 많아야 한 골을 득점할 수 있다. 경기가 끝난 후 적어도 한 팀이 골을 소수로 득점할 확률을 구하시오.
입력
첫째 줄에 A팀이 득점할 확률, 둘째 줄에 B팀이 득점할 확률이 퍼센트 단위로 주어진다. 퍼센트 단위로 주어지는 확률은 모두 0보다 크거나 같고 100보다 작거나 같은 정수이다.
출력
첫째 줄에 적어도 한 팀이 골을 소수로 득점할 확률을 출력한다. 정답과의 절대/상대 오차가 10-6이내인 경우에 정답이다.
알고리즘
- DP
- 경우의 수_확률
- 소수
풀이
- 경우의 수는 세부 경우의 수의 합으로 이루어져 있다
- 확률은 (경우의 수 * 확률) 세부 확률의 합으로 이루어짐
- 상태값은 시행횟수(idx), A의 점수, B의 점수 세 개로 잡는다
- 18번 모두 시행 했을 때, 소수인지 체크하는 것을 기저조건으로 설정
- doulbe 형의 경우
==연산자로 확인 불가 /> , <대소 비교로 풀이
코드
// BOJ - 1344 : 축구
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
const int n = 18;
double a, b, dp[20][20][20];
bool isP[20];
double go(int idx, int x, int y)
{
// 기저사례
if (idx == n) return isP[x] || isP[y] ? 1.0 : 0.0;
// 메모이제이션
double& res = dp[idx][x][y];
if (res > -0.5) return res;
res = 0.0;
// 로직
// 경우의 수는 모두 더하기
// 확률은 (경우의수 * 확률)을 모두 더하기
res += go(idx + 1, x + 1, y) * a * (1 - b); // x만 넣을 확률
res += go(idx + 1, x, y + 1) * (1 - a) * b; // y만 넣을 확률
res += go(idx + 1, x + 1, y + 1) * a * b; // x, y 둘다 넣을 확률
res += go(idx + 1, x, y) * (1 - a) * (1 - b); // x, y 둘다 못 넣을 확률
return res;
}
void era()
{
fill(isP, isP + 20, 1);
isP[0] = 0; isP[1] = 0;
for (int i = 2; i <= 20; i++)
{
for (int j = i + i; j <= 20; j += i)
{
isP[j] = 0;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf("%lf %lf", &a, &b);
a /= 100; b /= 100;
era();
memset(dp, -1, sizeof(dp)); // 초기화
printf("%.6lf", go(0, 0, 0));
return 0;
}
평가
- visual studio 컴파일러로는 컴파일되지 않는다 (왜,,,?)
- dp 문제의 4가지 풀이 방법을 다시 익히기
- 상태값을 올바르게 잡는 방법이 가장 중요
- 에라스토테네스체로 소수 배열 만들기
