백준 10163번: 색종이
문제 설명
- 각 도형이 최종적으로 보여지는 넓이를 구하는 문제입니다.
접근법
- 격자 크기만큼의 2차원 배열을 만듭니다.
- 색종이를 붙이는 순서를 활용합니다.
- 색종이가 붙여진 칸을 해당 색종이 순서로 바꿉니다.
- (x,y)에 1번 색종이가 붙여진 상태에서 나중에 5번 색종이가 (x,y)에 붙여지면 (x,y)의 값이 1에서 5로 바뀌면서 1번 색종이의 넓이가 1 줄어듭니다.
- 2차원 배열에서 1~N의 개수가 각 색종이의 넓이를 나타냅니다.
정답
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.parseInt(sc.nextLine());
int[] answer = new int[N+2];
int[][] board = new int[1001][1001];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(sc.nextLine(), " ");
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = x1 + Integer.parseInt(st.nextToken());
int y2 = y1 + Integer.parseInt(st.nextToken());
for (int j = x1; j < x2; j++) {
for (int j2 = y1; j2 < y2; j2++) {
board[j][j2] = i+1;
}
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if(board[i][j] == 0) continue;
answer[board[i][j]+1] ++;
}
}
for (int i = 2; i < N+2; i++) {
System.out.println(answer[i]);
}
}
}
기타
- 이번 색종이 문제도 정석적이지 않은 방법으로 접근하기 시작하면 정답에 도달하기 어려워 집니다.
- 시간복잡도를 생각해 보면 좋을 거 같은 문제입니다. 1000x1000 2차원 배열을 전부 고려하는게 비효율적으로 보일 수 있지만 3중반복문이 아니라 2중반복문을 2번 사용하기 때문에 1000x1000x2, 결국 O(N^2)이 소요되는 문제입니다.
처음 접근법
- 새로 종이가 추가될 때마다 이전 종이들과의 겹쳐진 부분을 확인해서 겹쳐져 있으면 너비를 빼는 방식으로 접근했고, 시간초과로 부분점수만 획득했습니다.
Author And Source
이 문제에 관하여(백준 10163번: 색종이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-10163번-색종이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)