import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st = null;
public static void main(String[] args) throws IOException {
int n;
long b;
long[][] matrix;
long[][] result;
Stack<Integer> stack = new Stack<>();
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
b = Long.parseLong(st.nextToken());
matrix = new long[n][n];
result = new long[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
matrix[i][j] = Long.parseLong(st.nextToken());
result[i][j] = matrix[i][j];
}
}
while (b > 0)
{
if (b % 2 == 1)
stack.add(1);
else
stack.add(0);
b /= 2;
}
stack.pop();
while (!stack.isEmpty()) {
long bit = stack.pop();
result = mul(result, result, n);
if (bit != 0) {
result = mul(result, matrix, n);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(result[i][j] % 1000 + " ");
}
System.out.println();
}
}
private static long[][] mul(long[][] matrix1, long[][] matrix2, int n) {
long[][] n_matrix;
n_matrix = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long result = 0;
for (int k = 0; k < n; k++) {
result += matrix1[i][k] * matrix2[k][j];
result %= 1000;
}
n_matrix[i][j] = result;
}
}
return (n_matrix);
}
}
문제에서 확인할 수 있듯이, 최대 행렬의 1000억 제곱까지 구해야 한다.
따라서 단순 Brute Force로 풀게 되면 시간이 팡팡 터지는 문제다.
그럼 어떻게 시간을 줄일 수 있을까?
개념은 정수의 N 거듭제곱 빠르게 구하기와 동일하다.
위 표는 11승을 구하는 방법이다.
11을 2진수로 표현하면 1011 이고, 이를 행렬 곱에 적용한다면 1일때 제곱을 한 뒤에 입력받은 행렬을 곱해준다.
0일때는 제곱만 한다.
조건은 매우 간단하다.
입력받은 B를 나눠서 2진수를 Stack에 담아주게 되면 최상위 비트부터 뽑아서 확인할 수 있다.
while (b > 0)
{
if (b % 2 == 1)
stack.add(1);
else
stack.add(0);
b /= 2;
}
다음 스택에서 무조건 한 개 꺼내준다.
그 이유는 다음과 같다. => 문제에서 주어지는 값이 최상위 비트가 항상 1임을 보장한다.
2. 왼쪽을 최대힙, 오른쪽을 최소힙으로 사용하고 최대힙 최소힙의 크기를 적절하게 유지하는 것이다.
적절하게 유지한다는 이야기는 연속된 수열을 대충 반으로 나눴을때 아래와 같이
1 2 3 / 4 5 6 과 같이 유지한다는 의미이며 문제의 조건에 따르면 중간값의 항상 최대힙의 top이 된다.
하나의 예를 들어서 설명해보겠다.
연속된 숫자가 다음과 같이 입력된다고 해보자.
1
5
2
10
-99
7
5
위와 같이 진행될 것이다. 그리고 추가로 최대힙의 top 값과 최소힙의 top 값은 항상 최소힙이 크거나 같도록 유지해야 한다.
그럼 알고리즘 정리를 해보겠다.
힙 크기 비교
최대힙의 크기와 최소힙의 크기가 같다면 최대힙에 숫자 삽입
아니면 최소힙에 숫자 삽입
최대힙 최소힙 top 값 비교
최대힙 top ≤ 최소힙 top → continue
최대힙 top > 최소힙 top → swap (최대힙 top, 최소힙 top)
최대힙 top 값 출력
import java.io.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st = null;
public static void main(String[] args) throws IOException {
int n;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.comparingInt(o -> -o));
n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
int num = Integer.parseInt(br.readLine());
if (maxHeap.size() == minHeap.size())
maxHeap.add(num);
else
minHeap.add(num);
if (!minHeap.isEmpty() && !maxHeap.isEmpty() && minHeap.peek() < maxHeap.peek())
{
int a = minHeap.poll();
int b = maxHeap.poll();
minHeap.add(b);
maxHeap.add(a);
}
System.out.println(maxHeap.peek());
}
}
}
