[ 백준 1344 ] 축구 ( C++ ) - DP

---

문제 링크

1344번: 축구

---

💡 문제 풀이

1. 90분이라는 시간이 있고, 5분마다 결과가 나온다 -> 최대 라운드는 18라운드가 있다고 할 수 있고, 최대로 넣을 수 있는 골도 18골이다. 따라서, dp[라운드][A팀의 골수][B팀의 골수] 를 만들어 준다.

2. 매번 A팀과 B팀이 골을 넣을 수 있는 확률은 독립실행이고, 이전 라운드 확률에서 곱해주면 된다.

 

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<vector>

using namespace std;

float A, B; // A와 B팀이 골을 넣을 확률
int sosu[] = { 2,3,5,7,11,13,17 }; // 18 이하의 소수의 집합
float dp[19][19][19]; // 총 라운드는 18개, A팀과 B팀이 넣을 수 있는 골도 18골

float play_game(int round, int a, int b) {

	if (round == 18) {
		for (int x : sosu) {
			if (a == x || b == x) {
				return 1;
			}
		}
		return 0;
	}
	if (dp[round][a][b]) return dp[round][a][b];

	// 순서대로 둘다 넣음, a만 넣음, b만 넣음, 둘다 못넣음 순.
	dp[round][a][b] += play_game(round + 1, a + 1, b + 1) * A * B;
	dp[round][a][b] += play_game(round + 1, a + 1, b) * A * (1 - B);
	dp[round][a][b] += play_game(round + 1, a, b + 1) * (1-A) * B;
	dp[round][a][b] += play_game(round + 1, a, b) * (1 - A) * (1 - B);

	return dp[round][a][b];
}

int main() {

	cin >> A >> B;
	A /= 100;
	B /= 100;

	cout << play_game(0, 0, 0);

	return 0;
}

---

🤔 문제 후기

처음에는 DP가 아닌 재귀 형식(DFS)으로 문제를 풀었는데, 이게 4가지의 경우가 있다 보니 4^18 이라는 너무 큰 가짓수가 나왔다. 하지만, 재귀형식을 비슷하게 DP로 풀면 대부분 해결된 경험으로 바로 DP로 시도해 봤는데, 문제가 바로 해결됐다.