[Beakjoon Online Judge] 1344 - 축구

I 문제 소개

---

문제

홍준이는 축구 경기를 보고 있다. 그러다가 홍준이는 역시 두 팀 중 적어도 한 팀이 골을 소수로 득점할 확률이 궁금해 졌다. 축구 경기는 90분동안 이루어지고, 분석을 쉽게하기 위해서 경기를 5분 간격으로 나눴다. 처음 간격은 처음 5분이고, 두 번째 간격은 그 다음 5분, 그리고 이런식으로 나눈다. 경기가 진행되는 동안 각 간격에서 A팀이 득점할 확률과 B팀이 득점할 확률이 주어진다. 그리고, 각 간격에서 두 팀은 각각 많아야 한 골을 득점할 수 있다. 경기가 끝난 후 적어도 한 팀이 골을 소수로 득점할 확률을 구하시오.

 

입력

첫째 줄에 A팀이 득점할 확률, 둘째 줄에 B팀이 득점할 확률이 퍼센트 단위로 주어진다. 퍼센트 단위로 주어지는 확률은 모두 0보다 크거나 같고 100보다 작거나 같은 정수이다.

 

출력

첫째 줄에 적어도 한 팀이 골을 소수로 득점할 확률을 출력한다. 정답과의 절대/상대 오차가 10^(-6)이내인 경우에 정답이다.

---

II 문제 풀이

---

 

이 문제는 solved.ac 기준 난이도 골드4의 그다지 복잡하지 않은 문제지만, 조금 수학적으로 풀어보았다.

 

먼저, "적어도 한 팀이 골을 소수로 득점할 확률"은 "두 팀 모두 골을 소수가 아닌 수로 득점할 확률"을 1에서 뺀 것과 같다.

그러면 두 팀 모두 소수가 아닌 수로 득점할 확률을 구하면 되겠다.

 

이 때, 한 팀당 90분동안 얻을 수 있는 최대 점수는 5분당 1점씩 총 18점이다.

따라서 0점 ~ 18점에서 소수가 아닌 수를 구해보자면, {0, 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18}이다.

 

A팀이 득점할 확률을 p라고 해보자. 그러면 A팀이 n의 점수를 얻을 확률은

p의 확률로 n번 득점해야하고, 나머지는 득점하지 못해야하므로

p^(n) * (1-p)^(18-n)인데, 득점을 하는 경우의 수는 여러가지 존재하므로 18Cn을 곱해주어야한다.(C : Combination)

 

따라서 A팀이 n의 점수를 얻을 확률은 p^(n) * (1-p)^(18-n) * 18Cn이고, n에 0부터 18 중에 소수가 아닌 수를 다 대입해서 더하면 A팀이 소수가 아닌 수로 득점할 확률이 나온다.

그 과정을 똑같이 B팀에도 적용해 두 확률을 곱하면 "두 팀 모두 소수가 아닌 수로 득점할 확률"이 나오고, 이를 1에서 빼면 문제에서 제시한 "적어도 한 팀이 골을 소수로 득점할 확률"이 나온다.

 

0. 초기 환경 설정

---

#include <iostream>

using namespace std;

int main(void)
{
	int A, B;
	int noSosu[12] = {0,1,4,6,8,9,10,12,14,15,16,18};

	cin >> A;
	cin >> B;
    
	return 0;
}

이번 문제는 main에서 해결하기 보다는 함수 위주로 작성해 풀었다.

소수의 경우 소수를 판단하게 작성할 수도 있겠지만, 수의 범위가 그다지 넓지 않아 계산이 훨씬 빠르게 하기 위해 직접 구해서 배열로 넣어놓았다.

 

1. comb 함수 작성(조합 계산)

---

 

double comb(int a, int n) // aCn 계산
{
	int i;
	double ans = 1;

	if (n > a / 2)
		n = a - n;

	int tempa = a;
	int tempb = n;
	for (i = 0;i < n;i++)
	{
		ans *= tempa;
		ans /= tempb;
		tempb -= 1;
		tempa -= 1;
	}
	return ans;
}

aCn의 경우 a를 하나씩 줄여가며 n번 곱한 것을 n을 한번씩 줄어가며 n번 곱한 것으로 나눠서 구한다.

(예를들어 5C2 = 5*4/2*1 = 10)

그런데, 5C3의 경우 5C2와 값이 같고, 5C4의 경우 5C1과 값이 같다. 즉, aCn은 aCa-n과 같다. 따라서 n이 a의 절반보다 클 때 n을 a-n으로 바꿔준다면 계산을 훨씬 빠르게 할 수 있다.

 

2. mpow 함수 작성(제곱수 계산)

---

math.h 헤더를 사용하면 pow()라는 함수를 쓸 수 있는데, 그걸 몰랐다.

pow라는 이름으로 함수를 작성했더니 재정의라고 오류가 뜨길래 아무생각 없이 mpow로 작성했다.

다음부터는 pow라는 함수를 적극 이용해야겠다.

 

double mpow(float a, int b) // a의 b제곱
{
	double ans = 1;
	int i;
	for (i = 0;i < b;i++)
		ans *= a;
	return ans;
}

 

3. scoreCal 함수 작성

---

double scoreCal(int num, int score) // 한번에 p의 확률로 골을 넣을 때 총 score만큼의 골을 넣을 확률
{
	double p = num;
	p /= 100;
	int n = score;
	double ans = mpow(p, n) * mpow(1 - p, 18 - n) * comb(18, n);
	return ans;
}

앞에서 말했던 p^(n) * (1-p)^(18-n) * 18Cn을 구해주는 함수다.

주의해야할 점은, 입력받은 값을 바로 넣으려고 num을 int형식으로 했기때문에

double p = num/100을 바로 정의해버리면 num/100이 통째로 int 처리가 되어버려 정상적인 입력 범위에서 p는 무조건 0 아니면 1이 나올 것이다. 따라서 한 줄 밑에서 p/=100을 계산해서 50이 입력되었을 때 0.5가 되게 하였다.

 

물론 num을 double로 받으면 되겠으나, 그러면 애초에 메인 함수에서 입력을 받을 때 double로 받게 해야했는데, 입력이 정수밖에 없다는데 double로 하기도 좀 그렇고 고치기도 귀찮아서 이렇게 했다.

 

4. 최종

---

#include <iostream>

using namespace std;

double comb(int a, int n) {} // aCn 계산

double mpow(float a, int b) {} // a의 b제곱

double scoreCal(int num, int score) {} // 한번에 p의 확률로 골을 넣을 때 총 score만큼의 골을 넣을 확률

int main(void)
{
	int A, B;
	int noSosu[12] = {0,1,4,6,8,9,10,12,14,15,16,18};

	cin >> A;
	cin >> B;

	double scoreA, scoreB;
	scoreA = scoreB = 0;
	int i;
	for (i = 0;i < 12;i++)
	{
		scoreA += scoreCal(A, noSosu[i]);
		scoreB += scoreCal(B, noSosu[i]);
	}

	double ans = 1 - scoreA * scoreB;
	cout << ans;

	return 0;
}

최종 함수이다. scoreA와 scoreB라는 변수를 만들어 각각 소수가 아닌 수들(noSosu[])로 점수를 얻을 확률을 반복문을 통해 더해줬고, 최종적으로 1에서 둘을 곱한 수를 빼 출력하게했다.

 

이러면 double의 특성상 소수점 아래 여섯자리까지 계산하는데, 문제에서 정답과의 절대/상대 오차가 10^(-6)이내면 다 맞게 한다고 했으므로 자리수를 늘려 계산할 필요 없이 딱 들어맞는다.

 

III 느낀점

---

사실 이 문제는 다이나믹 프로그래밍(DP)에 분류되는 문제라서 사실 DP를 공부해보려고 푼건데 어쩌다보니 조합론으로 풀어버렸다.

그리고 풀면서 C++에서는 pow()라는 함수를 지원한다는 사실도 알게 됐고, 오랜만에 수학 문제를 푸는 느낌이었어서 잠시 추억에 젖어봤다. (이정도면 수능 수학 3점짜리겠지..? 하면서 풀었다.)

 

최근 solved.ac 경험치작을 하려고 난이도 높은 문제를 몇 개 도전해봤는데 어렵기도 어려운데다가 풀지를 못하니 질려가는 느낌이었는데 수월한 문제를 푸니까 다시 의욕이 돋았다! 풀고 나서 다른 사람들이 DP로 푼 풀이들을 잠깐 보았는데 완전 생소해서 DP에 대해서는 공부를 한 다음에 관련 문제들을 풀어야겠다.

 

 

 

 

 

 

 

 

 

 

Coding Space by MIR :

Beakjoon Online Judge 1344번 축구 C++

BOJ 1344번 축구 C++

백준 1344번 축구 C++