[백준] 2563 색종이 (설명/코드/정답)

 

문제 링크 : https://www.acmicpc.net/problem/2563

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 128 MB

 

색종이를 하나 이상 붙인 후, 색종이가 덮은 검은 영역의 넓이를 구하는 프로그램을 작성.

 

• 도화지: 가로, 세로 크기가 각각 100인 정사각형의 흰색 도화지.
• 색종이: 가로, 세로 크기가 각각 10인 정사각형 모양의 검은색 색종이.
• 색종이 부착: 색종이의 변이 도화지의 변과 평행하도록 여러 개의 색종이를 도화지에 붙인다.

입력 :

• 첫째 줄: 색종이의 수 N (1 ≤ N ≤ 100)
• 둘째 줄부터: 각 색종이의 부착 위치를 나타내는 두 자연수 (각 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리, 아래쪽 변과 도화지의 아래쪽 변 사이의 거리)

출력 :

• 색종이가 덮은 검은 영역의 넓이를 출력.

 

 

 

 

 

2. 설계/검증 

grid와 cell

 

 

복잡도

시간 복잡도	최악의 경우	공간 복잡도
O(N)		O(N)

 

시간 복잡도는 O(cnt)로, 색종이 수가 많아져도 시간 증가가 선형적  시간 복잡도는 O(T * n)

 

도화지 크기가 고정되어 있어 추가적인 공간 사용은 없음 공간 복잡도는 O(1)  

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // 입력을 위한 객체 생성
        Scanner scan = new Scanner(System.in);

        int cnt = scan.nextInt(); // 색종이 수
        int[][] cell = new int[100][100]; // 도화지를 100*100개의 cell로 나눈 grid

        // 색종이 좌측 하단 꼭짓점 좌표
        for (int i = 0; i < cnt; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();

            // 색종이가 있는 cell을 1로 초기화
            for (int dx = x; dx < x + 10; dx++) {
                for (int dy = y; dy < y+10; dy++) {
                    cell[dx][dy] = 1;
                }
            }
        }

        // grid에 색종이가 있는 cell 모두 합하기
        int grid = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (cell[i][j] == 1) {
                    grid++;
                }
            }
        }

        // 결과출력
        System.out.println(grid);
        scan.close();
    }
}

 

 

.