목표 합을 가진 직사각형

직사각형은 행 구간과 열 구간으로 정해요

앞에서 행·열 번호와 새 좌표를 다뤘어요. 이번에는 좌표를 바꾸지 않고 일부 범위를 선택해요. topbottom행과 leftright열이 한 직사각형을 정해요. 두 끝을 모두 포함하고 한 칸도 직사각형이에요.

같은 합이어도 위치나 크기가 다르면 다른 선택이에요. top≤bottom, left≤right로 정하면 빈 범위를 제외하면서 모든 직사각형을 셀 수 있어요.

선택한 범위마다 합을 새로 시작해요

격자 {{1,-1},{2,0}}에서 첫 행 전체는 합 0, 오른쪽 열 전체는 합 −1, 전체 격자는 합 2예요.

합이 이미 target보다 크면 더 큰 범위도 모두 크다고 볼 수 있을까요? 음수 칸을 추가하면 합이 줄 수 있어요. 이번 제한은 작으므로 각 범위를 빠짐없이 열거하고 합을 계산할 수 있어요.

직접 풀어봐요

grid에서 적어도 한 칸을 포함하는 축에 평행한 직사각형을 골라요. 그 안 모든 값의 합이 target인 선택의 개수를 반환해요. 위치 또는 범위가 다르면 별도로 세요.

행·열 수는 각각 16, 원소는 −1010, target은 −360~360이에요. 모든 행의 길이는 같아요. 실행용 입력은 rows cols와 격자 값들, 마지막 줄 target이에요. 출력은 반환값이고 입출력은 하네스가 처리해요.

예시 1: grid={{1,2},{3,4}}, target=3 → 2. 값 3 한 칸과 첫 행 1+2 두 선택이에요. 예시 2: grid={{1,-1},{2,0}}, target=0 → 2. 첫 행 전체와 오른쪽 아래 0 한 칸 두 선택이에요.

2 2
1 2
3 4
3

2

2 2
1 -1
2 0
0

2