https://www.acmicpc.net/problem/2563
백준 2563번: 색종이
문제 풀이
가로와 세로 길이가 각각 100인 도화지가 있습니다. 이 도화지 위에 가로와 세로 크기가 각각 10인 색종이 N장을 붙입니다. 색종이는 도화지의 변과 평행하게 붙이며, 색종이가 겹칠 수 있습니다. 이 문제는 겹치는 부분을 고려하여 총 검은색 영역의 넓이를 계산하는 문제입니다.
수학적으로 푼다면 넓이를 계산하고 겹친 부분을 뺀다면 쉽게 구할 수 있으나, 해당 문제는 알고리즘으로 풀어야 합니다. 우선 도화지를 나타낼 배열을 [100][100] 크기로 생성합니다. 이때 타입은 boolean으로 하여 ture는 포함, false는 미포함으로 구분합니다.
즉, 어떤 수 x, y에 대해 배열[x][y]가 true이면 그 부분은 색종이가 붙어져 있다는 것을 뜻합니다.
입력 받은 색종이를 N개를 입력 받고, 색종이의 x, y이 주어지면 x, y ~ x + 9, x + 9까지 순회하면서 색종이를 붙입니다. 이때 이미 붙여진 색종이가 있다면 제외하고 붙였다면 넓이 값을 +1 해줍니다. 순회가 끝나면 총 넓이가 구해집니다.
코드
import java.util.Scanner;
public class Main {
private static final int SIZE = 100;
public static void main(String[] args) {
boolean[][] arr = new boolean[SIZE][SIZE];
int answer = 0;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
for (int j = x; j < x + 10; j++) {
for (int k = y; k < y + 10; k++) {
if (!arr[j][k]) {
arr[j][k] = true;
answer++;
}
}
}
}
System.out.print(answer);
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
백준 15990번: 1, 2, 3 더하기 5 (0) | 2025.01.13 |
---|---|
프로그래머스 n² 배열 자르기 (0) | 2024.07.12 |
프로그래머스 할인 행사 (0) | 2024.05.07 |
프로그래머스 괄호 회전하기 (0) | 2024.05.06 |
프로그래머스 귤 고르기 (0) | 2024.04.29 |