[백준] code.plus(브루트포스-비트마스크,JAVA)14391번, 종이 조각

문제 링크

14391번: 종이 조각

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. 종이를 자를 수 있는 모든 경우의 수를 탐색해야 합니다.

2. 종이의 가로와 세로를 조각한 최대의 합을 구해야 합니다.

 

배열

 

paper : 종이의 숫자를 저장하는 배열

 

check : 조각난 종이 자른 방향 저장 배열

 

재귀문과 paper, check 배열을 이용하여 종이를 조각하여 반복문을 통해 최대값을 구하였습니다.

 

종이를 조각내는 경우는 단순한 재귀를 통해 구현하였습니다.

 

종이의 최대값을 구할 때 가로는 왼쪽 -> 오른쪽, 세로는 위 -> 아래 방향으로 숫자를 만들어 더해지기 때문에

 

가로 형태로 조각난 종이는

 

현재까지 가로값 * 10 + 해당 지점 가로값 = 조각난 종이의 가로값으로 표현할 수 있습니다.

 

예를 들어

 

2 3 4

 

5 3 4

 

2, 3, 4가 가로로 잘렸을 때에

 

1. 2

 

2. 2 * 10 + 3 = 23

 

3. 23 * 10 + 4 = 234

 

위와 같이 가로로 표현할 수 있으며 세로로 조각난 종이도 동일하게 작동하도록 반복문을 사용하여 구현하였습니다.

 

 

문제에 해결알고리즘은

1. 종이의 숫자를 받습니다.

2. 재귀를 통해 경우의 수를 구하고 해당 경우의 수가 완성되었을 때 조각난 종이의 합을 구하였습니다.

3. 합을 구한 뒤 최대합과 비교하고 모든 경우의 수가 끝나면 조각난 종이의 최대합을 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 N,M을 저장하였습니다.
• 종이를 조각내는 모든 경우의 수를 구하는 dfs함수를 만들었습니다.
• 조각낸 종이의 합을 구하는 sum 함수를 만들었습니다.
• BufferedWriter에 조각난 종이의 최대합을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• dfs는 재귀를 반복하여 모든 경우의 수를 구하고 경우의 수가 완성되었을 때 sum함수를 실행하였습니다.
• sum은 반복문과 check[][]를 사용하여 합을 구하고 Math.max를 이용하여 최대합을 비교하였습니다.

※check가 true = 가로, false = 세로로 자른 것으로 나타냅니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N,M,max = Integer.MIN_VALUE;
	public static int[][] paper;	//종이의 들어갈 숫자 값
	public static boolean[][] check;	//종이 가로,세로 자른 방향
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //----------입력값 저장 및 배열 초기화------------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	paper = new int[N][M];
    	check = new boolean[N][M];
    	for(int i=0;i<N;i++) {
    		String str = br.readLine();
    		for(int j=0;j<M;j++) {
    			paper[i][j] = Character.getNumericValue(str.charAt(j));
    		}
    	}
    	dfs(0,0);		//함수 실행
    	bw.write(max + "\n");		//최대합 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //--------종이 조각내는 모든 경우 구하는 함수--------
    public static void dfs(int x, int y) {
    	if(x==N) {	//종이 조각내는 것 완성시 조각난 종이 합 구하기
    		sum();
    		return;
    	}
    	if(y==M) {	//해당 행 완료시 다음 행으로 이동
    		dfs(x+1,0);
    		return;
    	}
    	check[x][y] = true;		//가로로 잘랐을 때
    	dfs(x,y+1);
    	
    	check[x][y] = false;	//세로로 잘랐을 때
    	dfs(x,y+1);
    }
    //-------조각난 종이 합 구하는 함수--------
    public static void sum() {
    	int result = 0;
    	int temp;
    	for(int i=0;i<N;i++) {		//가로 합, 행 기준 탐색
    		temp = 0;
    		for(int j=0;j<M;j++) {
    			if(check[i][j]) {	//가로로 자른 값 연속할 때
    				temp *= 10;
    				temp += paper[i][j];
    			}else {		//세로로 자른 값 만났을 때
    				result += temp;
    				temp = 0;
    			}
    		}
    		result += temp;
    	}
    	for(int i=0;i<M;i++) {		//세로 합, 열 기준 탐색
    		temp = 0;
    		for(int j=0;j<N;j++) {
    			if(!check[j][i]) {	//세로로 자른 값 연속할 때
    				temp *= 10;
    				temp += paper[j][i];
    			}else {		//가로로 자른 값 만났을 때
    				result += temp;
    				temp = 0;
    			}
    		}
			result += temp;
    	}
    	max = Math.max(max, result);		//최대값 비교
    	return;
    }
}