백준 2563번: 색종이

문제 설명

• 완성된 도형의 총 넓이를 구하는 문제입니다.

접근법

• 도화지 크기만큼의 2차원 배열을 만듭니다.
• 색종이가 붙여진 칸을 1로 바꿉니다.
• 겹쳐져도 2가 아닌 1로 표시되기 때문에 아무런 문제가 없습니다.

정답

import java.util.*;

public class Main {

	public static void main(String[] args) {
		int answer = 0;
		int[][] board = new int[100][100];
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.nextLine());
		for (int t = 0; t < N; t++) {
			StringTokenizer st = new StringTokenizer(sc.nextLine()," ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			for (int i = r; i < r+10; i++) {
				for (int j = c; j < c+10; j++) {
					if(i>=100 || j>=100)continue;
					if(board[i][j] !=0)continue;
					board[i][j] = 1;
					answer++;
				}
			}
		}
		System.out.println(answer);
	}

}

기타

• 도화지 크기만큼 배열을 만들고 기록할 생각을 하지 못했습니다.
  • 완전탐색 혹은 전수조사를 해도 된다는 걸 아직 잘 캐치하지 못합니다.
• 위와 같은 방식으로 접근하지 못하면 문제가 굉장이 복잡해 집니다.

처음의 접근법

• 새로 종이가 추가될 때마다 이전 종이들과의 겹쳐진 부분을 확인해서, 겹쳐져 있으면 너비를 빼는 방식으로 접근했습니다.
• 하지만 두 번 이상 겹쳐지면 계산이 매우 복잡(사실상 불가능)해 지기 때문에 올바른 접근법이 아닙니다.