03 사전 체험용 코딩테스트 해설
2번 문제 - 색종이
일반적으로 해결하기 어려운 문제라도 여러 조건과 제약사항이 주어지면, 문제는 풀이가 가능한 범위로 축소될 수 있습니다. 이 문제에서는 아래와 같은 조건들로 인해 쉽게 해결할 수 있도록 변형할 수 있습니다.
- 모든 색종이와 도화지는 좌표축에 수직/수평한 방향으로 존재한다.
- 모든 색종이의 모서리는 정수좌표계 위에 존재한다.
- 도화지의 영역의 넓이가 100x100이다.
이 문제 뿐만 아니라 그림이나 일상적인 용어로 표현된 문제들 역시 결과적으로 어떤 값이 필요한가를 분석하여, 점점 이산적인 프로그래밍 문제로 추상화하고 간단한 계산 문제로 치환할 수 있습니다.
이 점을 유의하면서 문제의 해설을 들어봅시다.
Java
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.*;
import java.io.*;
public class Main{
public static final Scanner scanner = new Scanner(System.in);
public static void testCase(int caseIndex)
{
//색종이의 수를 입력받는다
int n = scanner.nextInt();
//100x100 도화지의 각 격자를 2차원 배열로 선언한다
int[][] paper = new int[100][100];
//paper[i][j] := (i행 j열)의 격자를 덮고 있는 색종이의 수라고 하자
//색종이들을 차례로 입력받아
//도화지의 각 격자를 갱신한다
for(int i = 0 ; i < n ; i ++)
{
//색종이가 커버할 도화지의 가장 왼쪽 아래 격자 좌표를 입력받는다
int sx = scanner.nextInt();
int sy = scanner.nextInt();
//가로 세로 10칸이므로 sx ~ sx+9, sy ~ sy+9까지의 영역을 지정한다
int ex = sx + 9;
int ey = sy + 9;
//해당 범위
for(int x = sx ; x <= ex; x++){
for(int y = sy; y <= ey; y++){
//색종이가 커버하는 각 칸에 대하여
//도화지의 해당 칸에 카운트를 누적한다
paper[y][x]++;
}
}
}
int area = 0;
for(int y = 0 ; y < 100; y++){
for(int x = 0 ; x < 100; x++){
if(paper[y][x] >= 1){
//하나 이상의 색종이가 커버하는 영역의 수를 센다
//그 영역의 수가 곧 넓이가 된다.
area ++;
}
}
}
System.out.println(area);
}
public static void main(String[] args)
{
//테스트케이스의 수를 입력받는다
int caseNum = scanner.nextInt();
//테스트케이스의 수 만큼 반복하여 처리한다
for(int caseIndex = 1 ; caseIndex <= caseNum; caseIndex++)
{
//테스트케이스를 하나의 함수로 분리한다
// => 초기화 등에 의한 실수를 줄일 수 있다.
testCase(caseIndex);
}
}
}실행하여 결과를 확인하세요!
