#2563 : 색종이

풀이방법

 

2023.03.19

도화지의 1x1 영역을 한 칸이라 생각해보자.

 

각 검은 색종이는 10x10 총 100칸을 차지한다.

주어지는 검은 색종이의 수는 최대 100장이다.

만약, 단순무식한 방법을 사용해서, 100장의 검은 색종이가 붙는 범위 총 10만 칸을 한 칸 한 칸 살펴서 정답을 알아낸다 해도,

우리는 (작은 상수) x 10만 번 정도의 연산만 하면 된다.

제한시간 내에 완료하기에 충분하고도 남는다.

 

그래서 그냥 단순무식한 방법으로 풀어보았다.

 

흰색 도화지의 어느 칸이 검은색으로 덮였고 어느 칸이 안 덮였는지 그 현황은 10x10 크기의 2차원 boolean 배열 plain에 저장하기로 하였다.

이 배열의 모든 칸의 초기값은 false이며

검은 색종이로 덮인 칸은 true, 덮이지 않은 칸은 false로 표시한다.

 

검은 색종이로 덮인 칸의 총 개수를 저장할 정수형 변수 answer를 선언하고, 0으로 초기화한다. 새로운 칸 하나가 검은 색종이로 덮일 때마다 answer의 값을 1씩 증가시킬 것이다.

 

각 검은 색종이의 위치가 주어질 때마다,

그 색종이가 덮는 100칸의 영역을 반복문을 통해 하나하나 모두 살핀다.

100칸 중에서,

이번에 살피는 칸이 true라면 이미 다른 검은 색종이에 의해 덮인 칸이다. 따라서 아무 행위도 하지 않고 다음 칸으로 넘어간다.

이번에 살피는 칸이 false라면 아직 덮이지 않은 칸이다. 따라서 해당 칸을 새롭게 true로 바꾸고, answer의 값을 1 증가시킨다.

 

이러한 과정을 모든 검은 색종이에 대해 끝냈다면, answer의 값을 화면에 출력한다.

 

 

코드

Java(2023.03.19)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//흰색 도화지의 현황을 저장할 boolean 배열 선언
		//false는 흰색, true는 검은색을 나타냄
		boolean[][] plain = new boolean[100][100];
		
		//검은 색종이의 개수 읽어와 저장하기
		Integer n = Integer.parseInt(br.readLine());
		
		//정답(검은 색종이에 덮인 칸 수)을 저장할 변수 선언 및 0으로 초기화
		Integer answer = 0;
		
		//N개의 검은 색종이에 대하여
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			Integer a = Integer.parseInt(st.nextToken());
			Integer b = Integer.parseInt(st.nextToken());
			
			//해당 정사각형의 왼쪽 위 모서리 == plain[100-b-10] [a]
			//해당 정사각형이 덮는 10x10 범위의 각 칸에 대하여
			for(int j=100-b-10; j<100-b; j++) {
				for(int k=a; k<a+10; k++) {
					//해당 칸이 이미 다른 검은 색종이에 덮여있다면 그냥 continue;
					if(plain[j][k]) continue;
					//그렇지 않다면 true로 바꾸고 answer을 1 증가시킴
					plain[j][k] = true; answer++;
				}
			}
		}
		
		//정답 출력
		System.out.print(answer);

	}

}