백준 1992 쿼드트리

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

실버2나 실버1이나 실버3이나 다 똑같은 수준이라서 실버1로 껑충.. ㅎㅎ

이문제의 특성은 압축이 안되면 "(" 로 시작해서 ")"로 닫아주는게 핵심

메인 로직

  1. 압축 검사하기
    1.1 검사 통과하면 0이나 1로 압축된값 더해주고 return
    1.2 통과하지 못하면 2번으로
  2. 4분할로 나눠서 좌표 나눠주고 "(" 추가후 재귀 (1번로직을 타게끔)
  3. 재귀가 끝나면 ")" 추가
import java.io.*;
import java.util.*;
public class 쿼드트리 {

	static int[][] array;
	static int N;
	static StringBuilder sb;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		array = new int[N][N];
		for(int i=0;i<N;i++) {
			String line = br.readLine();
			for(int j=0;j<N;j++) {
				array[i][j] = line.charAt(j)-'0';
			}
		}
		sb= new StringBuilder();
		
		cd(0,0,N);
		
		System.out.println(sb);
	}

	public static void cd(int x,int y, int length) {
		if(length==1) {
			sb.append(array[x][y]);
			return ;
		}
		
		int sum = 0;
		for(int i=x;i<x+length;i++) {
			for(int j=y;j<y+length;j++) {
				sum += array[i][j];
			}
		}
		if(sum==0) {
			sb.append("0");
			return;
		}
		if(sum==length*length) {
			sb.append("1");
			return;
		}
		
		int ql = length/2;
		sb.append("(");
		for(int i=0;i<2;i++) {
			cd(x+(i*ql),y,ql);
			cd(x+(i*ql),y+ql,ql);
		}
		sb.append(")");
	}
}

번아웃이 온..일주일 ㅎㅎ;;

다시 열심히달려보자..

좋은 웹페이지 즐겨찾기