Leetcode 를 풀어 보았다.

Pick One 버튼을 눌러 문제를 하나 뽑아왔다.

2088. Count Fertile Pyramids in a Land

Description 은 읽기 귀찮아서 예시 입력을 먼저 보았다.

피라미드와 인버스 피라미드 형태가 몇 개 있는지 세어 주는 문제인 듯 하다.

DP 문제가 아닐까? 행이 하나씩 추가되면 이전 결과값에 답을 더해가기 때문이다.

f(n) = f(n-1) + (새로 만든 피라미드) + (이어 붙인 피라미드)

• 새로 만든 피라미드는 단순히 ㅗ 모양임을 확인하면 된다.
• 이어 붙인 피라미드는 밑변의 길이를 메모하고 있어야 해서, g 라는 배열 하나를 더 추가한다.
• 인버스 피라미드는 grid 를 뒤집으면 되기 때문에 피라미드 문제만 풀면 된다.

그리드의 크기 제한을 확인했다.

1 <= m, n <= 1000
1 <= m * n <= 1e5

O(n^2) 인거 같으니 계속 하기로 한다...

func countPyramids(_ grid: [[Int]]) -> Int {
    var n = grid.count
    var m = grid[0].count
    
    func count(_ grid: [[Int]]) -> Int {

        var f = Array(repeating: 0, count: n)
        var g = Array(repeating: 0, count: m) // 현재 밑변의 길이가 2*g[k] - 1 인 피라미드의 중심이 여기에 있다.

        for i in 1..<n {
            f[i] = f[i-1]

            // Existing pyramid

            for j in 0..<m {
                if g[j] != 0 {
                    if j-g[j] >= 0,
                       j+g[j] < m,
                       Array(grid[i][(j-g[j])...(j+g[j])]) == Array(repeating: 1, count: 2*g[j] + 1) {
                        f[i] += 1
                        g[j] += 1
                    } else {
                        g[j] = 0
                    }
                }
            }
            
            // New pyramid

            for j in 1..<(m-1) {
                if grid[i][(j-1)...(j+1)] == [1, 1, 1], grid[i-1][j] == 1 {
                    f[i] += 1
                    g[j] = max(g[j], 2)
                }
            }
        }

        return f[n-1]
    }

    print(count(grid), count(grid.reversed()))
    return count(grid) + count(grid.reversed())
}

예제를 통과하지 못했다. 피라미드가 만들어지지 않는 조건을 추가했다.

guard n > 1, m > 2 else {
    return 0
}

그래도 통과가 안 된다. Existing pyramid 를 계산할 때 높이 4 짜리 피라미드가 높이 3짜리 피라미드를 동시에 포함하고 있음을 고려하지 못했다.

아래처럼 수정한다.

// Existing pyramid

for j in 0..<m {
    while g[j] >= 2 {
        if j-g[j] >= 0,
           j+g[j] < m,
           Array(grid[i][(j-g[j])...(j+g[j])]) == Array(repeating: 1, count: 2*g[j] + 1) {
            f[i] += g[j]-1
            g[j] += 1
            break
        } else {
            g[j] -= 1
        }
    }
}