(Python/파이썬) - 백준(BOJ) 25047번 : 사각형 게임 (Large)

https://www.acmicpc.net/problem/25047

25047번: 사각형 게임 (Large)

---

• 문제 : 

이 문제는 C번 사각형 게임 (Small) 문제와 N 제한만 다르고 동일한 문제입니다.

어느 날, 강의실에서 수업을 듣던 민우는 지루함을 참지 못하고 그만 노트에 N×N 크기의 격자를 그려버리고 말았습니다. 격자의 칸이 비어있으면 허전하니, 민우는 격자의 각 칸에 정수 Sij 도 써넣었습니다. 그러고 나서 민우는 옆자리에서 졸고 있던 종진이에게 간단한 게임을 제안했습니다. 게임의 규칙은 아래와 같습니다.

 

1. 민우가 먼저 N개의 행 중 0개 이상의 행을 고르고, 선택한 행에 속한 모든 칸들을 색칠합니다.
2. 그다음엔 종진이가 N개의 열 중 0개 이상의 열을 고르고, 선택한 열에 속한 모든 칸들을 색칠합니다.
3. 어떤 칸이 민우와 종진이에 의해 모두 색칠되었다면, 그 칸에 적힌 수만큼 종진이가 점수를 얻습니다.
4. 어떤 칸이 민우와 종진이에 의해 모두 색칠되지 않았다면, 그 칸에 적힌 수만큼 종진이가 점수를 얻습니다.
5. 어떤 칸이 민우나 종진이 중 한 명에게만 색칠되었다면, 그 칸에 적힌 수만큼 민우가 점수를 얻습니다.

 

민우와 종진이는 모두 자신의 점수가 최대가 되도록 최선의 전략을 이용해 게임을 할 것입니다. 이때 민우가 얻을 수 있는 최대 점수를 구해봅시다.

 

 

 

---

• 풀이 :

https://recordofwonseok.tistory.com/385?category=1000048

위 문제와 동일한 문제입니다. (풀이는 위 링크를 참고)

 

다만, N의 범위가 9 -> 18로 두 배 증가하여 시간초과를 회피하는 것이 중요한 문제였습니다.

다행이도 Small 문제를 효율적으로 잘 구성하여 이 문제 또한 pypy3으로 제출하여 한 번에 해결하였습니다.

 

 

 

---

• 소스코드 : 

from itertools import combinations
N = int(input())
board = [list(map(int,input().split())) for _ in range(N)]
nums = list(range(0,N))
C = list()
for i in range(N+1): # 민우가 선택가능한 행의 모든 경우의 수
    for x in combinations(nums,i):
        C.append(x)
answer = -(float("inf"))
s = list() # 모든 열의 합
for i in range(N):
    tmp = 0
    for j in range(N):
        tmp += board[j][i]
    s.append(tmp)

for row_comb in C: #민우가 행을 선택하는 모든 경우에 대해
    ans_tmp = 0 # 정답 후보
    for i in range(N): # 모든 열에 대하여
        tmp = 0
        # 해당 열에서 (민우가 선택한 열의 합) 과 (해당 열의 합) - (민우가 선택한 열의 합)이
        # 더 작은 경우를 정답에 더해주면 됨
        for rows in row_comb:
            tmp += board[rows][i]
        ans_tmp += min(s[i]-tmp , tmp)
    answer = max(ans_tmp,answer)
print(answer)