백준 2563 색종이 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/2563

2563번: 색종이

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

알고리즘 분류

• 구현

풀이

에잉 쯧..

처음에, x 별로 y최댓값, y최솟값 구해서 1차원 그래프로 풀었다가 틀렸다.

한 x 좌표에 색종이가 겹치지 않은 상태로 x1=10, y1=30,  x2=10, y2=80 같은 경우를 생각했어야 하는데,

큰 그림을 보지 못하고, 주어진 입력만 보고 단정 짓기 멈춰!

 

무튼, 이 문제는 2차원 그래프 graph[100][100]을 만들고, 색종이가 주어지면 색종이에 해당하는 칸들을 모두 check표시 하면서, 개수도 세어주면 된다. 당연히 이미 check된 칸은 개수를 중복으로 세지 않아야 한다!

 

코드

// 전체 도화지의 크기 100x100
// 색종이의 수  n <=100
// 색종이의 크기 10x10
fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var n = br.readLine().toInt()

    val graph = Array(100){BooleanArray(100)}
    var answer=0
    while(n--!=0){
        val (x,y) = br.readLine().split(' ').map { it.toInt() }
        for(i in x until x+10){
            for(j in y until y+10){
                if(graph[i][j]) continue
                graph[i][j]=true
                answer++
            }
        }
    }
    write("$answer")
    close()
}