백준 14846번 파이썬 문제풀이(직사각형과 쿼리)

---

해당 문제 dp적용할 점화식을 생각하기가 생각보다 까다로웠다. 해당 문제의 점화식은 다음과 같다.

 

어떠한 점 i, j 가 있으면 해당 지점까지 1~9 까지 개수를 3차원 dp에 dp[i][j][k] += 1로 (k는 해당 array[i][j] 의 값) 개수를 저장을 해놓는다. 그 후 개수를 누적해주기 위해 그 윗줄의 같은 행 즉 dp[i - 1][j] + 그 전열의 같은행 dp[i][j -1] 그리고 2번더해진 해당부분 dp[i -1][j -1]을 한번 빼주면 된다.

 

그 후 이렇게 저장된 dp의 값을 이용해 입력받은 4개의 점을 기준으로 1~10 까지 반복문을 돌면서

dp[x2][y2][k] - dp[x2][y1 - 1][k] - dp[x1-1][y2][k] + dp[x1-1][y1-1][k]

와 같은 형식으로 저장된 값들을 찾아주면 되나 저값들을 무작정 더하면 안되고 1 이상이라면 해당 수가 존재한다는 말이므로 정답 개수를 1개 추가하는 형식으로 구현 해주면 된다.

import sys

input = sys.stdin.readline

N = int(input())
array = [[0] * (N + 1)] + [[0] + list(map(int, input().split())) for _ in range(N)]

dp = [[[0] * 10 for _ in range(N + 1)] for _ in range(N + 1)]


for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, 10):
            if k == array[i][j]:
                dp[i][j][k] += 1
            dp[i][j][k] += dp[i-1][j][k] + dp[i][j-1][k] - dp[i-1][j-1][k]


Q = int(input())
for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    sum_ = 0
    for k in range(1, 10):
        if dp[x2][y2][k] - dp[x2][y1 - 1][k] - dp[x1-1][y2][k] + dp[x1-1][y1-1][k]:
            sum_ += 1
    print(sum_)