[BOJ 25047] 백준 25047번 - 사각형 게임 (Large)

		2022 DGIST 현풍전산배 알고리즘 대회 풀이
A		[BOJ 25044] 에어컨
B		[BOJ 25045] 비즈마켓
C		[BOJ 25046] 사각형 게임 (Small)
D		[BOJ 25047] 사각형 게임 (Large)
E		[BOJ 25048] 랜선 연결
F		[BOJ 25049] 뮤직 플레이리스트

1. 문제

$25047$. 사각형 게임 (Large) (2022 DGIST 현풍전산배 알고리즘 대회 D번)

백준 25047번 - 사각형 게임 (Large) (https://www.acmicpc.net/problem/25047)

2. 풀이

1. 민우가 먼저 $0\sim N$개의 행을 골라 색칠하고, 그 다음 종진이가 $0\sim N$개의 열을 고르고 색칠한다.
2. 어떤 칸을 한 명만 색칠한 경우 민우가 점수를 얻고, 그렇지 않은 경우 종진이가 점수를 얻는다.
3. 모두 자신의 점수가 최대가 되도록 최선의 전략으로 게임을 한다.

민우와 종진이가 취할 수 있는 행동의 경우의 수는 각각 $2^{18}$이므로, 총 경우의 수는 $2^{18}\times 2^{18}=2^{36}$=687억$이어서, 단순 브루트포스로 문제를 풀 수 없다.

---

처음에 민우가 $2^{18}$가지의 행동 중 어떤 행동을 한다. 위의 그림과 같이 $N=5$이고, 민우가 첫 번째, 세 번째, 네 번째 행을 선택한다고 가정하자. 그럼 종진이는 지금 주어진 환경에서 자신의 점수가 최대가 되도록 열을 선택할 것이다.

첫 번째 열을 골라 색칠한다면, (1, 3, 4)처럼 두 번 색칠하게 되는 칸은, 민우는 그만큼의 점수를 잃고 종진이는 그만큼의 점수를 얻는다. 마찬가지로 (3, 5)처럼 한 번 색칠하게 되는 칸은, 민우는 그만큼의 점수를 얻고 종진이는 그만큼의 점수를 잃는다.

종진이는 자신의 점수가 최대가 되도록 플레이하므로, 특정 열을 선택했을때 그 열을 색칠함으로서 변화하는 점수량이 양수이면, 해당 열을 칠하게 될 것이다. 따라서 두 번째 열과 세 번째 열을 칠하게 된다.

이렇게, 민우의 각각의 행동에 대해서 종진이가 취하는 행동이 단 하나로 고정되게 된다. 따라서, 종진이가 해당 행동을 취할 경우의 민우의 점수 변화를 계산하여 최댓값을 갱신하면, 정답을 구할 수 있다.

3. 채점 결과

4. 회고

.

5. 코드