백준 2571번 색종이-3 - SWIFT

문제

---

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다. 직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다. <그림 1>에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다.

 

반면 <그림 2> 에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다.

검은색 색종이의 수와 각 색종이를 붙인 위치가 주어질 때 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

첫째 줄에 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 출력한다.

 

문제 링크

https://www.acmicpc.net/problem/2571

 

 

풀이

---

도화지의 크기는 100 * 100으로 색종이는 이 밖을 벗어나게 붙이지 않는다.

이 말은 즉, 결국 검사하는 최대 크기는 100 * 100 크기라는 것이다.

하지만 그렇다고 10000개부터 1개까지 하나씩 줄여가며 전부 검사하게 된다면, 당연히 시간초과가 날 것이다.

그래서 조금 더 효율적으로 계산하기로 했다.

 

프로그램 동작

1. 가장 먼저 할 것은 색종이를 도화지에 붙이는 것이다.100 * 100은 너무 크기도 하고, 축약하면 이해가 잘 안될 거 같아 일부분만 그렸다.▼

 

2. 그 다음에는 높이의 누적합을 구해준다.

이 높이의 누적합은 결국 현재 칸의 높이를 알려준다.

위로 올라갈 수 있는 최대까지 올라가서 넓이를 구해야 최대 넓이를 구할 수 있다.▼

 

 

이제 우리는 세로 길이인 높이를 알았으니, 가로 길이만 구하면 된다.

각 y축에서 x값을 하나씩 늘려가며, 현재 칸의 높이와 누적된 가로 길이를 곱해주면 된다.▼

 

그러나 주의해야할 것이 있다.

누적합으로 계산하는 것은 좋은데, 만약 맨 처음 나온 누적합으로 계속 계산을 하게 되면, 값이 왜곡이 된다.▼

 

이런 경우가 발생할 수 있으므로, 현재 높이 누적합 보다 작은 높이 누적합이 나오면, 그 값을 기준으로 바꿔준다.

그 이후로 더 큰 값이 나와도, 지금까지 나온 높이 누적합들 중 가장 작은 값을 기준으로 값을 구한다.▼

 

3. 위 과정을 종이가 붙었다고 표시가 된 모든 좌표를 '시작점'으로 수행한다.

어느 위치에서 시작하느냐에 따라 값이 다르기 때문에 모든 지점을 시작점으로 재본다.

모든 지점을 다 검사한다고 해도, 최대 5천만번 검사를 하므로 시간내로 수행할 수 있다.▼

 

Swift 코드

---

let N = Int(readLine()!)!
var W = Array(repeating: Array(repeating: false, count: 100), count: 100)
var WH = Array(repeating: Array(repeating: 0, count: 100), count: 100)
var answer = 0
for _ in 0..<N {
    let B = readLine()!.split(separator: " ").map { Int(String($0))! }

    for i in 0..<10 {
        for j in 0..<10 {
            W[99 - B[1] - i][B[0] + j] = true
        }
    }
}

for i in 0..<100 {
    for j in 0..<100 {
        if W[i][j] && WH[i][j] == 0 {
            var h = 0
            for k in i..<100 {
                if !W[k][j] {
                    break
                }
                h += 1
                WH[k][j] += h
            }
        }
    }
}

for i in 0..<100 {
    for j in 0..<100 {
        if WH[i][j] != 0 {
            var m = WH[i][j]
            var w = 0
            for k in j..<100 {
                if WH[i][k] == 0 {
                    break
                } else {
                    m = min(m, WH[i][k])
                    w += 1
                    answer = max(answer, m * w)
                }
            }
        }
    }
}

print(answer)