Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- java
- Design Patterns
- Dxerr.h
- BOJ
- 10830번
- 1043번
- 1300번
- 클린코드
- 가장 긴 증가하는 부분 수열2
- 17장
- DxTrace
- Spring
- 냄새와 휴리스틱
- Adapater Pattern
- 9장
- 11758번
- 2156번
- Design Pattern
- 2206번
- 2166번
- programmers
- 코딩테스트
- SerialDate 리펙터링
- 자바의 정석
- java의 정석
- 11286번
- 백준
- springboot
- 코딩 테스트
- 프로그래머스
Archives
- Today
- Total
Don't give up!
[백준] 10830번 : 행렬 제곱 (java) 본문
어떻게 생각하고 문제를 풀었는가?
NxN 행렬 A의 B제곱은 x1+x2+....=B를 만족하는 A의 xi제곱들을 곱하여 나타낼 수 있습니다.
이때 xi의 값들이 2의 제곱으로 나타내어질 수 있도록 한다면 A의 제곱, 4제곱, 8제곱을 구하여 결과를 빠르게 구할 수 있습니다.
이러한 xi 값들은 B를 2진수로 표현하여 1을 갖는 자리를 확인함으로써 빠르게 찾아낼 수 있을 것이라고 생각하였습니다.
코드
import java.io.*;
import java.util.*;
class Main {
private static int N;
private static String bitmask;
private static int[][] A;
public static void main(String[] args) throws IOException {
readInput();
int[][] result = calculate();
printMatrix(result);
}
private static void readInput() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
N = Integer.parseInt(tokenizer.nextToken());
long B = Long.parseLong(tokenizer.nextToken());
bitmask = Long.toBinaryString(B);
A = new int[N][N];
for(int i=0; i<N; i++){
tokenizer = new StringTokenizer(reader.readLine());
for(int j=0; j<N; j++){
A[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
reader.close();
}
private static int[][] calculate(){
int[][] result = new int[N][N];
for(int i=0; i<N; i++){
result[i][i] = 1;
}
int index = bitmask.length()-1;
for(int i=0; i<bitmask.length(); i++){
if(i>0){
A = multiple(A, A);
}
if(bitmask.charAt(index--) == '1'){
result = multiple(result, A);
}
}
return result;
}
private static int[][] multiple(int[][] from, int[][] to){
int[][] result = new int[N][N];
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
for(int k=0; k<N; k++){
result[i][j] += from[i][k] * to[k][j];
}
result[i][j] = result[i][j] % 1000;
}
}
return result;
}
private static void printMatrix(int[][] target){
StringBuilder stringBuilder = new StringBuilder();
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
stringBuilder.append(target[i][j]);
stringBuilder.append(" ");
}
stringBuilder.append("\n");
}
System.out.println(stringBuilder);
}
}
B를 2진수로 만들어 필요한 A의 행렬 제곱을 계산하고, 결과에 곱하는 코드를 작성하였습니다.
주어진 문제에서 결과는 1000을 나눈 나머지의 값으로 원소를 표현해야 하는데, 주어진 입력이 1000이 될 경우를 미리 해결하여야 합니다.
이를 해결하고자 초기 행렬을 단위 행렬로 정의하고, 2^0부터 행렬 곱셈을 수행하도록 하였습니다.
행렬 곱셈을 하는 함수 multiple에서 행렬 곱셈의 결과를 다시 1000으로 나눈 나머지 값들로 선언하기 때문에 모든 결과는 1000보다 작은 값을 가질 수 있습니다.
'Coding Test > BOJ' 카테고리의 다른 글
[백준] 1300번 : K번째 수 (java) (0) | 2021.08.20 |
---|---|
[백준] 1541번 : 잃어버린 괄호 (java) (0) | 2021.08.17 |
[백준] 11758번 : CCW (java) (0) | 2021.08.16 |