2번 문제 - 색종이 - 실전 유형 코딩 테스트 모의고사

배우기

03 사전 체험용 코딩테스트 해설

2번 문제 - 색종이

일반적으로 해결하기 어려운 문제라도 여러 조건과 제약사항이 주어지면, 문제는 풀이가 가능한 범위로 축소될 수 있습니다. 이 문제에서는 아래와 같은 조건들로 인해 쉽게 해결할 수 있도록 변형할 수 있습니다.

모든 색종이와 도화지는 좌표축에 수직/수평한 방향으로 존재한다.
모든 색종이의 모서리는 정수좌표계 위에 존재한다.
도화지의 영역의 넓이가 100x100이다.

이 문제 뿐만 아니라 그림이나 일상적인 용어로 표현된 문제들 역시 결과적으로 어떤 값이 필요한가를 분석하여, 점점 이산적인 프로그래밍 문제로 추상화하고 간단한 계산 문제로 치환할 수 있습니다.

이 점을 유의하면서 문제의 해설을 들어봅시다.


import java.util.*;
import java.io.*;

public class Main{
    public static final Scanner scanner = new Scanner(System.in);
    
    
    public static void testCase(int caseIndex)
    {
        //색종이의 수를 입력받는다 
        int n = scanner.nextInt();
        
        //100x100 도화지의 각 격자를 2차원 배열로 선언한다
        int[][] paper = new int[100][100];
        
        //paper[i][j] := (i행 j열)의 격자를 덮고 있는 색종이의 수라고 하자
        
        //색종이들을 차례로 입력받아
        //도화지의 각 격자를 갱신한다
        for(int i = 0 ; i < n ; i ++)
        {
            //색종이가 커버할 도화지의 가장 왼쪽 아래 격자 좌표를 입력받는다 
            int sx = scanner.nextInt();
            int sy = scanner.nextInt();
            
            //가로 세로 10칸이므로 sx ~ sx+9, sy ~ sy+9까지의 영역을 지정한다
            int ex = sx + 9;
            int ey = sy + 9;
            
            //해당 범위
            for(int x = sx ; x <= ex; x++){
                for(int y = sy; y <= ey; y++){
                    //색종이가 커버하는 각 칸에 대하여 
                    
                    //도화지의 해당 칸에 카운트를 누적한다
                    paper[y][x]++;
                }
            }
        }
        
        
        int area = 0;
        for(int y = 0 ; y < 100; y++){
            for(int x = 0 ; x < 100; x++){
                if(paper[y][x] >= 1){
                    //하나 이상의 색종이가 커버하는 영역의 수를 센다
                    //그 영역의 수가 곧 넓이가 된다.
                    area ++;
                }
            }
        }
        
        System.out.println(area);
    }
    
    public static void main(String[] args)
    {
        //테스트케이스의 수를 입력받는다
        int caseNum = scanner.nextInt();
        
        //테스트케이스의 수 만큼 반복하여 처리한다 
        for(int caseIndex = 1 ; caseIndex <= caseNum; caseIndex++) 
        {   
            //테스트케이스를 하나의 함수로 분리한다
            // => 초기화 등에 의한 실수를 줄일 수 있다.
            testCase(caseIndex);
        }
    }
    
    
}

java

실습 내용

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

<도화지 위에 놓인 세 색종이>

실행 조건

실행시간은 1초 이내이다.

입력 조건

첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스의 첫 줄에는 색종이의 수 N이 1과 100사이의 자연수로 공백없이 주어진다.

이후 N줄에 걸쳐서 각 색종이의 정보가 공백으로 구분된 두 정수로 주어진다.

첫 번째 숫자는 색종이의 왼쪽 변과 도화지의 왼쪽 벽 사이의 거리이다
두 번째 숫자는 색종이의 아랫쪽 변과 도화지의 아랫쪽 변 사이의 거리이다.
모든 색종이는 도화지의 영역을 벗어나지 않는다.

출력 조건

각 테스트케이스에 대하여 색종이가 차지하는 넓이를 한 줄에 공백 없는 정수로 출력한다.

문제 출처

정보올림피아드

입/출력 예시

공백

줄 바꿈

탭

예시 1

입력

2
3
37
157
52
4
37
52
157
1314

출력

260
336

⋇ 입출력 형식을 잘 지켜주세요

질문하기

추가 자료

추가 자료가 없습니다

여기서 새로운 학습 자료를 확인하세요!
선생님이 추가한 자료들을 바로 확인할 수 있어요.