[BOJ 25046] 백준 25046번 - 사각형 게임 (Small)

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

1. 문제

$25046$. 사각형 게임 (Small) (2022 DGIST 현풍전산배 알고리즘 대회 C번)

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

2. 풀이

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

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

각각의 모든 경우에 대해 민우가 얻을 수 있는 최대 점수를 갱신하면, 정답을 구할 수 있다.

나는 ‘D. 사각형 게임 (Large)’ 문제와 한번에 해결했기 때문에, 밑의 코드는 단순 브루트포스로 해결한 코드가 아니라, 좀더 개선된 $D$번 코드이다. $D$번 해설에서 자세한 내용을 설명하고자 한다.

3. 채점 결과

4. 회고

문제의 $1/sim 5$ 규칙을 계속 반복적으로 수행하는 것으로 착각하고 문제를 어떻게 풀어야할지 감이 안왔었다. 알고보니 $1/sim 5$를 딱 한 번만 수행하는 것이었다.

5. 코드