22882번 - 시험 문제 출제 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 127 | 64 | 58 | 66.667% |
문제
덕인 교수는 알고리즘 과목을 강의하는 교수다. 덕인 교수는 다가오는 중간고사 시험 문제를 준비하면서, 얼마 전 학생들에게 가르친 최대 부분합 문제를 추가하기로 했다. 최대 부분합 문제는 다음과 같다.
- 배열 $A=[a_1, a_2, \dots , a_n]$가 주어질 때, $max_{1 \leq i \leq j \leq n}(\sum_{k=i}^{j}a_k)$를 구하여라.
덕인 교수는 수열 하나를 주고, 해당 수열에서 최대 부분합을 구하도록 할 심산이다. 덕인 교수는 수열 제작의 대가로, 다음과 같은 과정으로 수열을 만든다고 알려져 있다.
- 정수만으로 구성된 $N \times N$ 크기의 이차원 배열을 준비한다.
- $(1, 1)$에서 출발해 아래 혹은 오른쪽으로 이동하는 것을 반복하여 $(N, N)$에 도착한다. 참고로 $(i, j)$에서 아래로 이동하면 $(i+1, j)$에 도달하고, 오른쪽으로 이동하면 $(i, j+1)$에 도달한다.
- 지나온 칸에 적힌 정수를 지나온 순서대로 나열하여 길이 $2N-1$의 수열을 완성한다.
덕인 교수는 '답이 $K$인 문제는 아름다운 문제'라는 신념을 가지고 있어서, 최대 부분합이 $K$인 수열을 만들려고 한다. 여기에 더해서, 최대 부분합이 $K$인 수열을 최대한 많은 방법으로 만들려고 한다. 덕인 교수의 조교인 당신은 $N \times N$ 크기의 이차원 배열이 주어지면, 최대 부분합이 $K$인 수열을 만드는 서로 다른 방법의 수를 구해야 한다. 어떤 두 방법이 서로 다르다는 것은 두 수열을 구성하는 이차원 배열상의 경로가 서로 다르다는 것을 의미한다.
입력
첫 번째 줄에는 이차원 배열의 크기 $N$과 만들고자 하는 최대 부분합 $K$가 주어진다. $(1 \leq N \leq 20, -4 \times 10^{10} \leq K \leq $ $4 \times 10^{10})$
그 다음 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. 구체적으로, $i$번째 줄의 $j$번째 정수는 이차원 배열 $A$의 $(i, j)$에 위치하는 $A_{i,j}$를 의미한다. $(-10^9 \leq A_{i,j} \leq 10^9)$
출력
주어진 배열에서 최대 부분합이 $K$인 수열을 만드는 서로 다른 방법의 수를 출력한다.
예제 입력 1
3 3 1 2 -5 -2 3 0 -1 -1 1
예제 출력 1
2
예제 입력 2
4 3 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1
예제 출력 2
4
노트
첫 번째 예제에서 만들 수 있는 수열들은 다음과 같다.
- $[1, 2, -5, 0, 1]$
- $[1, 2, 3, 0, 1]$
- $[1, 2, 3, -1, 1]$
- $[1, -2, 3, 0, 1]$
- $[1, -2, 3, -1, 1]$
- $[1, -2, -1, -1, 1]$
이 중에서 최대 부분합이 3인 수열은 1번째와 5번째 수열뿐이므로 답으로 2를 출력한다.
두 번째 예제에서는 만들 수 있는 수열들 중 $[1, -1, 1, 1, 1, -1, 1]$만이 최대 부분합이 3이고, 이러한 수열을 만들기 위해서는 $(1, 2)$와 $(4, 3)$을 반드시 지나야 하므로 경우의 수는 4가 된다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호