백준 14846번: 직사각형과 쿼리

백준 14846번: 직사각형과 쿼리

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] * 11 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, 11):
            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, 11):
        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_)

모 기업 코테에서 나왔던 문제와 유사한 문제라고 해서 풀어봤다. 나는 해당 코테에서는 손을 못 댄 문제였어서 풀어봄. 전공 과목에서 비슷한 방식으로 탐색해서 값을 구하는 걸 배웠던 기억은 어렴풋이 나는데 잘 기억이 안나서 dp 점화식 세우기가 어려웠다. 그래서 다른 분들 풀이를 참고했다. 1~10까지의 숫자를 따로 체크하는 배열을 써야할지, 어떻게 해야할지 고민을 했는데 dp를 3차원으로 해서 각 숫자에 대해 체크해주면 되는 거였다. 즉, input값에 대해서 각 숫자 1~10의 범위에 대해 (0,0)~(i,j)까지 출연한 갯수를 dp[i][j][k]에 넣어주고, Q로 x1,y1,x2,y2 범위를 받아준 후에 해당 사각형 범위 내에 각 숫자 1~10에 대해 출연한 갯수가 1번 이상이면 sum을 더해주어서 최종 sum을 구하는 것이다. dp는 풀어도 풀어도 익숙해지지가 않아서 정말 많이 연습해봐야될 것 같다.