[백준] 25046번 / 25047번: 사각형 게임 Java

 

문제

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

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

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

 

입력

첫 번째 줄에는 격자판의 크기를 의미하는 정수 N이 주어집니다. (small : 1≤N≤9)  , (lagre : 1≤N≤18) 

두 번째 줄부터 N+1 번째 줄에는 절댓값이 10^9 보다 작거나 같은 N개의 정수가 공백으로 구분되어 주어집니다. i+1 번째 줄에서 j 번째로 주어진 정수는 격자판의 (i,j) 칸에 적힌 수 S(i,j) 를 의미합니다.

 

출력

첫 번째 줄에 민우가 얻을 수 있는 최대 점수를 출력합니다.

 

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

25046번: 사각형 게임 (Small)

 

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

25047번: 사각형 게임 (Large)

접근

비트마스크와 완전탐색을 통해 해결할 수 있는 문제입니다.

비트마스크를 사용하려면 경험상 2가지 조건이 맞아야 사용합니다.

1) 집합의 부분 함수를 표시할 때

2) 집합의 원소 개수가 작을 때 (최대 63개, Long.MAX_VALUE의 bitcount 개수)

 

small의 경우는 n의 최대값이 9, large의 경우는 n의 최대값이 18이므로 비트마스크를 사용할 수 있습니다.

 

비트마스크를 이용하여 민우가 행을 선택하는 모든 경우를 조사합니다.

민우가 행을 선택하면, 종진이가 열을 선택합니다.

이 때, 종진이는 최선의 전략을 선택함으로 가장 점수가 높은 전략을 채택해야 합니다.

 

종진이가 열을 선택할지 말지의 결정은 다음과 같습니다.

 

선택하고자 하는 열에서 행이 선택된 곳(1)과 선택되지 않은 곳(2)이 있다면,

1) 종진이가 열을 선택하는 경우,  (1)의 점수는 얻고, (2)의 점수는 얻지 못합니다.

2) 종진이가 열을 선택하지 않는 경우, (1)의 점수는 얻지 못하고, (2)의 점수를 얻습니다.

 

따라서 열을 선택하는 경우의 점수는 (1)의 합 vs (2)의 합 중 큰 값을 취합니다.

민우의 점수는 자연스럽게 (1)의 합 vs (2)의 합 중 작은 값을 취합니다.

 

모든 열에 대해 민우의 점수를 합산하고,

이 중 최대값을 출력합니다.

 

* 격자의 칸에는 절대값이 10^9 이하입니다.

  따라서 최대 점수의 초기값이 -(10^9)*18*18 보다 작아야 합니다.

  (이거 때문에 0으로 줬다가 계속 틀렸습니다 ㅠㅠ 조건을 잘 읽어보도록 합시다.)

 

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	//https://www.acmicpc.net/problem/25046
	//https://www.acmicpc.net/problem/25047
	
	static int N;
	static long[][] Board;
	static final long INF = Long.MAX_VALUE;
	
	public static long calScore(long minwoo) {
		//민우 점수
		long score = 0;
		//열 탐색
		for(int i=0;i<N;i++) {
			//칠한 점수
			long onScore = 0;
			//안 칠한 점수
			long offScore = 0;
			//행탐색
			for(int j=0;j<N;j++) {
				int idx = 1<<j;
				//색을 칠한 경우
				if((minwoo&idx)==idx){
					onScore+=Board[j][i];
				//안 칠한 경우
				}else {
					offScore+=Board[j][i];
				}
			}
			//종진이가 색을 칠하면 offScore를,
			//색을 칠하지 않으면 onScore를 얻음 
			//큰 값은 종진이가, 작은 값은 민우가 얻음
			score+=Math.min(onScore, offScore);
		}
		//민우 점수 리턴
		return score;
	}
	
	public static long getMaxScore() {
		//점수를 -INF로 초기화
		long score=-INF;
		//완전탐색, 비트마스크 사용
		long bitMask = 1<<N;
		//행 칠하는 경우의 수
		for(long i=0;i<bitMask;i++) {
			//최대 점수를 취함
			score=Math.max(score, calScore(i));
		}
		//출력
		return score;
	}
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); //게임판 크기
		Board=new long[N][N];
		StringTokenizer st;
		//배열 입력
		for(int i=0;i<N;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				Board[i][j]=Long.parseLong(st.nextToken());
			}
		}
		//출력
		System.out.println(getMaxScore());
		br.close();
	}
}