[알고리즘 문제] ColorPaper

import java.util.Scanner;

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

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int y, x, width, height;

        int[][] ary = new int[102][102]; // 전체 배열
        int[] extent = new int[n + 1]; // 각 색종이의 넓이를 계산하는 배열

        for (int i = 1; i <= n; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            width = sc.nextInt();
            height = sc.nextInt();

            for (int a = 0; a < height; a++) {
                for (int b = 0; b < width; b++) {
                    ary[y + a][x + b] = i; // n번쨰 색종이가 차지하는 영역을 색칠
                }
            }
        }

        for (int q = 0; q < 102; q++) {
            for (int w = 0; w < 102; w++) {
                extent[ary[q][w]] += 1; // 색종이가 칠해진 영역의 넓이는 계산
            }
        }

        for (int s = 1; s <= n; s++) {
            System.out.println(extent[s]);
        }

    }
}

나름 문제를 보고 재미있을 것 같다고 생각했던 문제이다.

여러 색종이가 겹쳐질 수 있다는 조건으로 놓여질 때, 각각의 색종이의 넓이를 구하는 문제이다. 여기서 중요한 것은 아래쪽 색종이는 넓이는 구할 때 겹쳐진 부분을 제외하고 넓이는 구해야 한다. 마지막에 올라간 색종이는 겹쳐지는 부분이 없으므로 그대로의 넓이를 가질 수 있다.

 

7x5는 35의 넓이는 가지는데, 이는 1x1의 넓이는 가진 정사각형을 7x5사각형에 모두 35개를 채울 수 있다는 의미이다. 위의 문제도 넓이가 주어진 공간에서 얼마나 차지하는지를 구하면 되는 문제라고 생각했다. 

 

첫번째 for문에서 n번째 색종이가 차지하는 영역을 표시해주었다. 단, 여기서 겹치는 부분은 이후에 놓여지는 색종이의 번호로 덮히게 된다. 

두번째 for문에서는 ary배열을 순환하면서 인덱스의 값(몇번째 색종이인 지 알 수 있음)을 가져오고 이 값을 extent의 인덱스로 사용하여 extent배열에서 해당 인덱스의 값을 하나씩 증가시켜 주었다. 이렇게 되면 각 색종이마다 차지하는 넓이는 계산할 수 있다.