일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
- BinarySearch
- 항해99
- 99클럽
- 스프링
- 알고리즘
- BFS
- 그리디
- 정렬
- 완전탐색
- DP
- 자바
- 프로그래머스
- 개발자취업
- 브루트포스
- 동적 프로그래밍
- 네트워크 계층
- lower bound
- 트리
- Spring
- Java
- 그래프
- 코딩테스트준비
- 백트래킹
- Til
- 스프링 핵심 원리 - 기본편
- 그래프 이론
- 우선순위큐
- 데이터베이스
- DFS
- 백준
- Today
- Total
AtraFelis's Develop Diary
[백준] 2563 - 색종이 (JAVA) 본문
문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.
입력
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
출력
첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.
풀이
문제를 봤을 때 가장 먼저 가장 먼저 생각난 구현법은
- 중복된 부분을 생각하지 않고, 전체 색종이의 넓이를 구한다. 예를 들어,
n=10
이면 사용한 색종이의 넓이는1000
이 된다. - 중복된 부분을 찾아 그 부분의 넓이를 전체 넓이에서 빼준다.
이것이다.
하지만, 이 방법은 조금 고민해보면 2번에서 문제가 생긴다는 것을 깨달을 수 있다.
이런 식으로 색종이가 세 번 이상 겹친다면?
중복되는 영역에 몇 개의 색종이가 겹쳐 있는지 어떻게 알 수 있을까? 알 수 있다고 해도 구현도 어렵고, 매우 비효율적일 것 같다.
그렇다면 어떻게 해야할까?
언제나 그렇듯이 이런 문제는 고민한 시간에 비해 해결 방법은 간단했다.
2차원 배열을 이용하는 것이다. $100 \times 100$의 2차원 배열을 만든 후 색종이가 차지하는 영역만큼 배열에 체크한다
예를 들어 int 배열이라면 전부 0으로 채우고, 색종이가 들어간 부분만 1로 표시하면 된다.
boolean 배열이라면 색종이가 들어간 부분만 true로 표시한다.
$1 \times 1$ 크기의 정사각형을 2차원 배열의 하나의 원소로 생각하는 것이다.
이렇게 하면 배열에서 체크된 부분의 넓이만을 구하면 되므로, 중복된 부분을 따로 고려할 필요가 없어진다.
코드
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 {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk;
boolean[][] paper = new boolean[100][100];
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
int x = Integer.parseInt(stk.nextToken());
int y = Integer.parseInt(stk.nextToken());
for (int j = 0; j < 10; j++) {
for (int k = 0; k < 10; k++) {
paper[j + x][k + y] = true;
}
}
}
int answer = 0;
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if(paper[i][j]) answer++;
}
}
System.out.println(answer);
}
}
'Algorithm > 백준' 카테고리의 다른 글
[99클럽 코테 스터디 1일차 TIL / 백준] 2776 - 암기왕 (JAVA) (0) | 2025.01.13 |
---|---|
[백준] 1010 - 다리 놓기(JAVA) (0) | 2025.01.07 |
[백준] 10815 - 숫자 카드 (JAVA) (0) | 2024.12.30 |
[백준] 1389 - 케빈 베이컨의 6단계 법칙 (C언어) (0) | 2024.07.10 |
[백준] 1149 - RGB거리 (C언어) (0) | 2024.07.03 |