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

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

25046번: 사각형 게임 (Small)

---

• 문제 : 

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

 

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

 

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

 

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

 

 

 

---

• 풀이 :

문제분류는 비트마스킹으로 되어있지만 조합론을 사용하여 해결한 문제입니다.

combinations 모듈을 사용하여 0부터 N-1까지의 수를 0부터 N번 뽑는 모든 경우를 C 배열에 저장했습니다.

 

처음 풀이는 다음과 같숩니다.

 

민우가 행을 선택하는 모든 경우들에 대해 종진이가 열을 선택하는 모든 경우의 조합으로 해당 민우의 최대점수를 구한다.

 

위 방법은 절대로 답이 될 수 없습니다.

 

우선, 시간초과의 문제입니다. 민우가 행을 선택하는 경우의 수 (2^N)-1 에 대해 종진이가 열을 선택하는 모든 경우의 수 (2^N)-1번을 수행하고 각 수행마다 n^2의 보드 탐색을 실시해야 합니다. 당연히 시간초과가 발생하게 됩니다.

 

두번째로, 위 방법은 애초에 정답을 도출할 수 없는 알고리즘입니다. 모든 경우들 중 민우가 최대점수를 얻는 경우를 찾는 문제였다면 위 로직으로 정답을 구할 수 있었을 것입니다

그러나 종진이도 최대점수를 얻기 위해 최선의 선택을 고려하므로 모든 경우를 탐색하면 정답을 도출할 수 없습니다.

 

 

두 번째 풀이입니다.

 

위의 종진이도 최대점수를 얻기 위해 최선의 선택을 고려한다. 에 초점을 두어 어떻게 하먄 해결할 수 있을지 고민했습니다.

 

여기서 핵심은, 종진이는 각 열마다 항상 민우보다 높은 점수를 가져갈 수 있다는 점입니다.

예를 들어, 아래와 같은 보드가 주어질 때 민우가 0, 1 번째 행을 선택했다면

 

5 3 2
3 2 1
2 4 3

 

0번째 열에서는 5+3 과 2중 더 큰 값을,

1번째 열에서는 3+2 와 4중 더 큰 값을,

2번째 열에서는 2+1 과 3중 더 큰 값을 가져가면 됩니다.

결론적으로, 종진이는 각 열마다 (민우가 선택한 행의 합) 과 (민우가 선택하지 않은 행의 합) 중 더 큰 값에 해당하는 점수를 가져가면 됩니다.

 

이제 문제 해결 알고리즘의 흐름입니다.

 

1. combinations 모듈을 사용해 민우가 선택할 모든 열의 조합을 저장

 

2. 모든 열의 합을 s 배열에 저장, 이 값은 선택하지 않은 행의 합을 구하기 위함

 

3. 1번에서 구한 모든 조합에 대해 각 케이스마다 모든 열을 순회하며 max(선택한 행의 합, 선택하지 않은 행의 합) 값을 구하고 이 값들 중 가장 큰 값을 찾음 

 

 

추가 ) board에서 주어지는 값의 범위가 0 이상이 아닌 절댓값이 10^9 이하인 수 입니다. 따라서 음수를 처리해주기 위해 answer의 초깃값을 - 무한대로 지정해주어야 합니다.

 

 

---

• 소스코드 : 

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)