2563번 색종이

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

 

이 문제는 아래 그림에 주어지는 것과 같이

100*100 사이즈의 도화지에 검은색 색종이를 붙이는데, 이 색종이가 붙은 부분의 넓이를 구하는 문제이다.

 

이, 때 색종이의  크기는 10*10으로 고정이고 도화지 바깥으로 나가는 경우는 없다.

 

3장의 색종이가 주어진 예제

해당 이미지에서 주어진 입력은 아래와 같고,

3
3 7
15 7
5 2

 

출력되는 결과는

260

 

이 나오게 된다.

 

이 문제는 정말 하루종일 고민을 했었는데 결론적으론 내가 문제를 제대로 안 읽어서 일어난 일이었다.

문제를 풀기 위해 여러 가지 고민을 했는데,

 

1. 어차피 색종이의 총넓이는 N*100이다 여기서 겹치는 부분을 계산해서 빼면 된다.

2. 이중배열을 이용하는 문제니 깐 배열에 주어진 가로세로 길이를 넣고 하나씩 꺼내서 비교하자

3. 그다음 겹치는 부분을 계산해서 그 넓이를 구하고 총넓이의 값에 빼주자

 

이렇게 생각하고 길고 복잡한 코드를 짰다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = n * 100;

        int w = 0;
        int h = 0;

        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        int count = 0;
        for (int i = 0; i < n-1; i++) {
            for (int j = count; j < n-1; j++) {
                w = Math.abs(arr[i][0] - arr[j+1][0]);
                h = Math.abs(arr[i][1] - arr[j+1][1]);
                if (w < 10 && h < 10) {
                    result -= ((w*2)*(h*2));
                }
            }
            count++;
        }
        System.out.println(result);

    }
}

 

당연하게도 바로 틀렸다.

딱 첫 번째 주어진  예제만 통과할 수 있는  코드였기 때문에 당연한 결과였다.

 

이 문제를 가지고 머리를 싸매고 고민하다가 친구가 왜 이걸 못 푸냐고 힌트를 줬는데

어차피 도화지의 크기는 정해져 있으니깐 배열로 도화지를 그리고 색종이의 위치에 맞게 1을 넣으면 되지 않냐고 했다.

 

도화지의  크기가 정해져 있다고?

 

전혀 생각하지 못했다.

도화지의 크기가 정해져 있다는 게 문제에 써져 있는데 그것도 제대로 안 읽고 삽질하고 있었다.

그래서 바로 코드를 모두 지우고 새롭게 다시 작성했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        int[][] arr = new int[100][100]; // 가로 세로 크기가 각각 100인 도화지

        int h,w;

        for (int i = 0; i < n; i++) {
            h = sc.nextInt();
            w = sc.nextInt();
            for (int j = h; j < h+10; j++) {
                for (int k = w; k < w + 10; k++) {
                    arr[j][k]++;
                }
            }
        }

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (arr[i][j] == 0) {
                    continue;
                }
                result++;
            }
        }

        System.out.println(result);
    }
}

 

먼저 처음 배열에 도화지의 크기를 집어넣고,

가로세로를 입력받을 때마다 해당 위치에  1 씩 값을 더해줬다.

 

모든 작업이 끝나고 이제 값이 1 이상인 부분의 합을 구하고 출력한다.

 

아니면 어차피 면적만 구하는 거니깐 boolean 값을 써줘도 된다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        boolean[][] arr = new boolean[100][100]; // 가로 세로 크기가 각각 100인 도화지

        int h,w;

        for (int i = 0; i < n; i++) {
            h = sc.nextInt();
            w = sc.nextInt();
            for (int j = h; j < h+10; j++) {
                for (int k = w; k < w + 10; k++) {
                    arr[j][k] = true;
                }
            }
        }

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (arr[i][j]) {
                    result++;
                }
            }
        }

        System.out.println(result);
    }
}

 

boolean로 수정하면 더 적은 메모리를 먹을 줄 알았는데

	메모리	시간
int	17944 kb	188 ms
boolean	17740 kb	180 ms

 

생각보다 그렇게 유의미한 결과는 안 나왔다.

 

아무튼 다음부턴 문제를 제대로 읽어야겠다.