19242번 - 행렬 합 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (하단 참고) | 256 MB | 88 | 14 | 10 | 14.493% |
문제
N행 M열로 이루어질 정수 행렬 A와 정수 x가 주어진다. 행렬 A의 모든 부분행렬 중 그 합이 x를 넘지 않는 (즉, x 이하인) 부분행렬의 개수를 구하고 싶다. 예를 들어 N = M = 2 이고 x = 5, 그리고 A가 아래와 같은 예를 생각해보자.
1 2 3 4
이 경우, 1x1 크기의 총 네 개의 부분행렬은 모두 그 원소의 합이 x = 5 이하이다. 1 과 3을 포함한 2x1 크기의 부분행렬과 1과 2를 포함한 1x2 크기의 부분행렬도 각각 원소의 합이 1+3 = 4 그리고 1+2 = 3으로 x 이하이므로 조건을 만족한다. 다른 부분행렬은 원소의 총 합이 5를 초과하므로, 이 경우 답은 6이 된다.
다른 예로, N = 2, M = 3, x = 0 이며 A가 아래와 같은 행렬인 경우를 생각해보자.
0 -1 -2 -3 -4 -5
이 경우, A의 모든 부분행렬의 원소 총 합이 0 이하이므로 답은 18이 된다.
N, M, x 그리고 A를 입력으로 받아, 원소의 총 합이 x이하인 부분행렬의 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스 첫 줄에는 N, M, x 가 공백으로 구분되어 주어진다.
다음 N줄에 걸쳐 각 줄에 M개의 정수가 공백으로 구분되어 주어진다.
출력
상기한대로 A의 부분행렬 중 원소의 총 합이 x이하인 부분행렬의 개수를 출력한다.
제한
- 1 ≤ T ≤ 10
- -1,000,000,000 ≤ x ≤ 1,000,000,000
- -100,000 ≤ A의 각 원소 ≤ 100,000
서브태스크 1 (6점)
- 1 ≤ N ≤ 50
- 1 ≤ M ≤ 50
서브태스크 2 (18점)
- 1 ≤ N ≤ 300
- 1 ≤ M ≤ 150
예제 입력 1
4 2 2 5 1 2 3 4 2 3 0 0 -1 -2 -3 -4 -5 4 1 3 1 2 1 2 3 3 1 10 10 10 10 -100 10 10 10 10
예제 출력 1
6 18 7 16
- 테스트 케이스 1과 2: 문제에서 다루었다.
- 테스트 케이스 3: 4행 1열의 행렬이며, 1x1 크기의 부분행렬은 모두 원소의 합이 3 이하이므로 조건을 만족한다. 1과 2를 하나씩 포함한 2x1 크기의 부분행렬 세 개도 총합이 3이므로 조건을 만족하여 답은 7이다.
- 테스트 케이스 4: 총합이 1 이하가 되기 위해서는 부분행렬이 -100을 반드시 포함하여야 하며, -100을 포함한 모든 부분행렬이 조건을 만족하므로 답은 16이 된다.
시간 제한
- Java 8: 3 초
- Python 3: 8 초
- PyPy3: 8 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Python 2: 8 초
- PyPy2: 8 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호