*완전탐색* colorpaper

완전 탐색 알고리즘 문제입니다.

핵심

문제가 어려워 보일 수 있으나, 단순한 문제이다. 0으로 된 배 열위에 값을 입력받고, 그 값이 몇 번 나왔는지 체크하는 것이다.

 

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[][] arr = new int[101][101];
        int n = sc.nextInt();
        for (int i=1;i<=n;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            for (int k =b; k <b+y; k++){
            for (int j = a; j<a+x; j++){
                    arr[k][j]=i;
            }
        }
        }
        int[] count = new int[n+1];
            for (int j=0;j<101;j++){
                for (int k =0; k<101; k++){
                    count[arr[j][k]]++;
                }
        }
        for (int i=1; i<=n; i++){
            System.out.println(count[i]);
        }
    }
}

 

해설

가로와 세로가 최대 101칸이 사용 가능하다. 따라서 이중 배열의 크기를 [101][101]로 잡았다.(0~101)

for문에서 i가 1부터 시작하는 이유는 첫 번째 색종이를 1로 표현하기 위함이다.

차례대로 a, b, x, y를 받고 가로는 a부터 a+x 까지 숫자를 대입하고, 세로는 b부터 y까지 대입해준다.

즉 원하는 직사각형 모양대로 수를 대입한다.

이후 배열에 저장된 값들의 count를 세기 위해 count배열을 선언한다.

각 배열 위치에 저장된 값을 count로 세어준다.

이후 첫 번째 색종이부터 count를 출력한다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.