[백준 15724번] 주지수 (python)

문제

 

네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 주지수를 만들기 위해서 일정한 직사각형 범위 내에 살고 있는 사람 수를 참고 자료로 쓰고 싶어한다.

진경대왕은 굉장히 근엄한 왕이기 때문에 당신에게 4개의 숫자로 직사각형 범위를 알려줄 것이다.

예를 들어, 위와 같이 사람이 살고 있다고 가정할 때 <그림 1>의 직사각형 범위의 사람 수를 알고 싶다면 진경대왕은 네 개의 정수 1 1 3 2를 부를 것이다. 마찬가지로 <그림 2>는 1 1 1 4, <그림 3>은 1 1 4 4가 될 것이다.

진경대왕을 위하여 이 참고 자료를 만들어내는 프로그램을 작성해보자.

 

기록

(dp 9일차) 어제 엄청 비슷한 문제를 풀어서 그대로 풀었다. 어제 정성껏 풀이 작성햇는데 거의 같다고 보면 될 것 같아서 링크를 걸어놓으려고 한다. 어제는 재귀로 풀었는데 오늘은 반복문으로 풀어봤다.

>> 2021.07.30 - [분류 전체보기] - [백준 11660번] 구간 합 구하기 5 (python)

 

코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
box = [list(map(int, input().split())) for i in range(N)]

# (1, 1)부터 (x, y) 영역의 합 저장할 dp 생성
dp = [[0]*(M+1) for i in range(N+1)]
for x in range(1, N+1):
    for y in range(1, M+1):
        dp[x][y] = box[x-1][y-1]+dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1]

# 각 테스트케이스의 영역 합 출력
K = int(input())
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1])

1. dp배열에 (1, 1)부터 (x, y) 영역의 합을 저장한다. 점화식은 dp[x][y] = (x,y)칸값 + dp[x-1][y] + dp[x][y-1] - dp[x-1][y-1]

2. 각 테스트케이스의 영역 합을 계산하여 출력한다.