백준 2563 <색종이>

색종이의 수가 100이하이고 흰색도화지 크기가 100이기때문에 완전탐색으로도 가능한 문제이다.

 

그렇지 않다면 인덱스 트리를 이용해서 풀어야하는 문제이다.

 

이 문제의 시간 복잡도를 계산한다면 최대 색종이의 수*도화지의 크기*색종이의 크기 이므로 100000 10만이 될것이다.

 

이러한 문제는 시간복잡도를 게산하면서 풀면 더욱 도움이 될것이다.

 

문제 해결순서

1. boolean형 visit 2차원 배열에 각각의 색종이 시작점으로 부터 10크기만큼 체크해준다
2. 겹치는 부분이면 어차피 true기때문에 신경 안써줘도 됨
3. 마지막에 전체 도화지 크기에 몇개의 true가 있는지 확인

전체 코드

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

public class Main{

	static boolean visit[][];
	static int n;
	public static void main(String[] args) throws IOException {
		visit=new boolean[101][101];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			for(int j=0;j<10;j++) {
				for(int k=0;k<10;k++) {
					visit[x+j][y+k]=true;
				}
			}
		}
		int count=0;
		for (int i = 0; i < 101; i++) {
			for (int j = 0; j < 101; j++) {
				if(visit[i][j]) {
					count++;
				}
			}
		}
		System.out.println(count);

	}
}