Paper Piece

문제 복기

비트마스킹 단원에서 문제를 접해서 비트마스킹으로 풀었지만, 문제만 딱 봤을 때 어떻게 비트마스킹을 떠올릴 수 있을까?

비트마스킹으로 문제 풀 수 있는 경우 =>문제에서 n이 주어지고, 그 중 일부를 선택하는 경우!

문제 설명

알고리즘 생각

1. 항상 3자리보다 4자리가 크니까, 4자리 수 씩 잘라서 합을 구하면 되지 않을까? =>반례 존재! 아래의 경우 가로든 세로 4개씩 자르면 5005가 최대합이 되지만, 500(3자리), 5000(4자리) 이렇게 자르면 최대합이 5500이 된다! 0005 0000 0000 5000

2. NM은 최대 4이므로 4x4크기에 0부터 15까지 수를 다 채운다고 생각한다. 2^16 < 1억이므로 모든 경우를 다 구해봐도 된다.

비트마스킹으로 풀기

1. for(int i=0;i<(n*m);i++) : 모든 부분수열 다 구한다.

2. 가로인 경우:0, 세로인 경우:1이라고 하고, 가로일 때 가로 합을 구하고, 세로일 때 세로합을 구해서 둘을 더한다.=>가로합과 세로합을 어떻게 구할 수 있을까? 4x4 크기에 0부터 15까지 숫자를 채워넣으면, 숫자들의 규칙성을 따져보면 (i,j)에 있는 수 = i*m+j (m은 주어진 종이의 가로크기) 가 되는 것을 알 수 있다.

3. 그러므로 우리가 확인해야할 수 k = i*m+j가 된다.

4. 가로 수 합 : 가로에 대해서 가로수합을 구하기 때문에 행을 의미하는 i-for문 마다 cur을 0으로 해준다. 수가 추가될 때마다 현재의 cur*10 + a[i][j]. 중간에 세로(1)을 만나면 sum에 현재까지의 cur을 더해주고 cur은 다시 0으로 초기화해준다. 행과열에 대해 n,m for문을 다 돌고나면 행 for문을 나가기 전ㅇ에 현재까지의 cur를 sum에 한번 더 더해준다. 왜냐하면 세로를 만날 때만 sum에 더하기 때문에 for문을 나가기 전에(cur변수의 스코프를 벗어나기 전에)세로를 만나지 않고 더한 cur를 sum에 더해주어야 한다!

5. 세로 수 합: 가로수합과 동일하게 세로 기준으로 합을 구해주면 된다.

6. i-for문에서 각각의 부분수열에서 sum 4,5에서 구한 가로 수 합, 세로 수 합을 다 더한 값이 된다.

7. 최종 정답은 sum의 최댓값을 구하는 것이기 때문에, i-for문을 벗어나기 전에 sum의 최댓값을 ans에 넣어주고 나온다.

import java.util.*;
public class PaperPiece {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[][] a = new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j] = sc.nextInt();
			}
		}
		//비트마스킹.
		int ans=0;
		for(int s=0;s<(1<<(n*m));s++) {
			int sum=0;//각각의 경우의 합.
			//1.가로수 구하기.
			for(int i=0;i<n;i++) {
				int cur=0;//현재 가로에 대해서 가로수를 구해야하기 때문에 n-for문 밑에 있어야함!
				for(int j=0;j<m;j++) {
					int k=i*m+j;
					if((s&(1<<k))==0) {cur = cur*10+a[i][j];}//가로일 때 합.
					else {sum+=cur;cur=0;}
				}
				sum += cur;//for문 나가기 전에, 세로 만나지 않았을 때 마지막에 현재까지의 cur 더해준다.
			}
			//2.세로수 구하기.
			for(int j=0;j<m;j++) {
				int cur=0;
				for(int i=0;i<n;i++) {
					int k=i*m+j;
					if((s&(1<<k))!=0) {cur = cur*10+a[i][j];}
					else {sum+=cur;cur=0;}
				}
				sum+=cur;//가로를 만나지 않았을 때 마지막에 현재까지의 cur 더해준다. 
			}
			//sum에는 가로합과 세로합이 다 더해져있다.
			ans = Math.max(ans, sum);
			//sum이 있는 for문을 나가기 전에 최댓값을 비교해서 ans에 저장해서 for문 스코프 밖으로 나간다.
		}
		System.out.println(ans);
	}

}