문제
N×N 격자의 각 셀에 정수가 주어진다. 각 행을 두 그룹 A, B로 분류하고 각 열마다 min(A열 합, B열 합)을 더해 최종 점수를 최대화한다.
입력
- 첫째 줄: N (1 ≤ N ≤ 20)
- 이후 N줄: 각 행의 N개 정수 (-10^9 ≤ 값 ≤ 10^9)
출력
최대 점수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 1 2 3 4 | 4 |
풀이
N개의 행을 A그룹과 B그룹으로 나누는 방법은 2^N가지이다. 각 분류에 대해 N개의 열마다 A그룹 행 합과 B그룹 행 합 중 작은 값을 합산한다. 모든 분류를 비트마스크로 열거하여 최대값을 구한다.
- 0부터
(1 << N) - 1까지 모든 비트마스크i를 순회한다. - 각 비트마스크에서 비트가 1인 행은 그룹 A, 0인 행은 그룹 B로 분류한다.
- 각 열
j에 대해 A그룹 행들의 합a와 B그룹 행들의 합b를 계산한다. - 해당 열의 점수
min(a, b)를 누적한다. - 모든 비트마스크 중 최대 점수를 출력한다.
핵심 아이디어: 행의 그룹 분류를 비트마스크로 표현하면 2^N가지 분류를 간결하게 열거할 수 있다. 비트 AND 연산 (idx & (1 << j)) > 0으로 j번째 행이 A그룹인지 B그룹인지 O(1)에 판별한다. N ≤ 20이면 2^20 = 1,048,576가지이므로 브루트포스가 가능하다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day91BOJ25046사각형게임구현 { // 25046 사각형 게임
static int N;
static long ans;
static long[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = Long.MIN_VALUE; // 최대값을 찾기 위한
map = new long[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
map[i][j] = Long.parseLong(st.nextToken());
}
for (int i = 0; i < (1 << N); i++)
ans = Math.max(ans, sol(i, 0));
System.out.println(ans);
br.close();
}
private static long sol(int idx, long tmp) {
for (int i = 0; i < N; i++) {
long a = 0, b = 0;
for (int j = 0 ; j < N; j++) {
if ((idx & 1 << j) > 0) a += map[j][i];
else b += map[j][i];
}
tmp += Math.min(a, b);
}
return tmp;
}
}복잡도
- 시간: O(2^N * N^2) — 2^N가지 분류 × 각 분류에서 N×N 합산
- 공간: O(N^2) — N×N 격자 저장