[백준] 1344번 축구 C++ 코드

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int prime[21];
double a,b, dp[20][20][20];

// 소수 찾기
void primenum() {
  prime[0] = 0;
  prime[1] = 0;
  for(int i = 2; i*i < 21; i++) {
    int j = 2;
    while(i * j < 21) {
      prime[i * j] = 0;
      j++;
    }
  }
}

double go(int x, int y, int idx) {
  // 90분이 경기 종료, 경기 종료 후에 골 수 확인
  if(idx == 18) return prime[x] || prime[y] ? 1.0 : 0.0; 
  double &ret = dp[x][y][idx];
  if(ret > -0.5) return ret; // double형은 == 이 어려움. 따라서 부등호 사용
  ret = 0.0; // 경우의 수 찾기
  ret += go(x + 1, y, idx + 1) * a * (1 - b); // x만 넣는 경우
  ret += go(x + 1, y + 1, idx + 1) * a * b; // x,y 둘 다 넣는 경우
  ret += go(x, y + 1, idx + 1) * (1 - a) * b; // y만 넣는 경우
  ret += go(x , y, idx + 1) * (1 - a) * (1 - b); // 둘 다 못 넣는 경우
  return ret;
}

int main() {
  cout << fixed;
  cout.precision(12); // 소수점 12자리까지 출력
  cin >> a >> b;
  // 확률 찾기
  a /= 100;
  b /= 100;
  // 테이블 초기화
  memset(dp, -1, sizeof(dp));
  // 소수찾기 위함
  fill(prime, prime + 21, 1);
  primenum();
  cout << go(0,0,0) << '\n';

  return 0;
}

풀이

경우의 수 찾기 문제이다. 확률을 구한 다음, 4가지 경우의 수를 모두 찾아서 더하면 된다. 메모이제이션 할 때 주의점은 double형은 등호로 확인이 불가능에 가깝다. 따라서 부등호를 사용해서 확인해야한다. 절대 안나올 값을 비교해주면 된다. 그리고 90분이 되었을 때 둘 중 한 팀이라도 소수 득점을 했다면 1.0, 그게 아니라면 0.0을 반환해 확률을 구해주면 된다.