[백준/1566] P배열 (Python)

Problem : https://www.acmicpc.net/problem/1566

1566번: P배열

 

Difficulty : Gold 3

 

Status : Solved (pypy3)

 

Time : 00:26:21

 

---

 

문제 설명

 

 

정수로 이루어진 2차원 배열이 P배열이 되려면, 각각의 열에 있는 원소의 합과, 행에 있는 원소의 합이 모두 0보다 커야 한다.

예를 들어,

 

2  1 -1
-1  2  2

 

는 P배열이지만, 

 

 1  1 -1
-1  2  2

 

는 P배열이 아니다.

세준이는 어떤 행이나 열을 선택한 다음에, 그 행이나 열의 모든 원소의 부호를 바꿀 수 있다. (-1을 곱한다.) 이차원 배열이 주어졌을 때, 이 배열을 P배열로 만들기 위해서 필요한 선택의 회수의 최솟값을 구하는 프로그램을 작성하시오. 

 

 

입력 및 출력

 

입력

 

첫째 줄에 배열의 행의 개수 N과 열의 개수 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 수가 주어진다. N과 M은 18보다 작거나 같고, 이차원 배열에 있는 수는 -26보다 크거나 같고, 35보다 작거나 같은 정수이다.

 

출력

 

첫째 줄에 정답을 출력한다. 만약 불가능 할 때에는 -1을 출력한다.

 

입력 예시

 

2 2
-26 2
2 1

 

출력 예시

 

2

 

 

---

 

풀이

 

언뜻 보면 매우 많을 것 같지만, 실제 경우의 수는 2^18 * 2^18 = 2^36 이 된다. 약 10^11인 셈이다.

 

여기에 모든 경우의 수를 테스트하기보단, 적절한 가지치기를 시행해볼 수 있다. 모든 M 조합에 대해 처음 조합을 고정해 놓고, i번째 열(1 <= i <= N)에 대하여 M조합을 적용한 합을 구한다. P배열 조건을 만족하려면 그 합이 0 초과이어야 하므로, 만약 합이 0보다 크다면 다음 열로, 그렇지 않으면 그 열 전체를 뒤집는 두 가지 경우밖에 발생하지 않는다. (P합이 0이라면 바로 탐색을 종료할 수 있다. 아무리 뒤집어도 0이기 때문) 마지막 배열에 도달했을 경우, 각 열의 합이 P배열의 조건을 만족하는지 검사하도록 한다. 즉 사실상 탐색 조합이 절반으로 줄어드므로 2^18 * 2^9 = 2^27 이 된다. 10^8 정도이며, 도중에 합이 0이 되어 탐색이 종료되면 경우의 수는 더 줄어든다. 즉 브루트포스를 적용해봄직하다.

 

풀이 코드

import sys
MAX = float('inf')
input = sys.stdin.readline

N, M = map(int, input().split())
P_list = [list(map(int, input().split())) for _ in range(N)]
answer = MAX
p_col = [0]*M

def dfs(n_idx, m_num) :
  if n_idx == N :
    for i in range(M) :
      if p_col[i] <= 0 :
        return MAX
    return 0
  p_row = [0]*M
  for i in range(M-1, -1, -1) :
    p_row[i] = -P_list[n_idx][i] if m_num & (1 << i) else P_list[n_idx][i]

  sum_row = sum(p_row)
  if sum_row == 0 :
    return MAX
  for i in range(M) :
    p_col[i] += p_row[i] if sum_row > 0 else -p_row[i]
  result = dfs(n_idx+1, m_num)
  if sum_row < 0 :
    result += 1
  for i in range(M) :
    p_col[i] -= p_row[i] if sum_row > 0 else -p_row[i]
  return result

for i in range(1 << M) :
  answer = min(answer, dfs(0, i) + bin(i)[2:].count('1'))
print(answer if answer < MAX else -1)

풀이 완료!