10830번 - 행렬 제곱
문제 풀이 시간 : 1시간
문제 요약
- 크기가 N * N인 행렬 A가 있다.
- A의 B제곱을 구하라.
- 각 원소를 1,000 으로 나눈 나머지를 출력한다.
- 2 ≤ N ≤ 5
- 1 ≤ B ≤ 100,000,000,000
문제 풀이
옛날에 풀려고 문제를 읽었다가 B의 범위를 보고 바로 도망쳤던 문제이다.
뭐 풀지 찾아보다가 뭔가 풀 수 있을 것 같아서 이번에 풀게 되었다.
행렬의 제곱을 할 때, 1제곱 * 1제곱을 하면 2제곱,
2제곱 * 2제곱를 하면 4제곱이 나온다.
이걸 이용해서 분할정복법을 사용하면 B도 많이 작아지게되지 않을까?
라는 생각으로 코드를 짰다.
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static long B;
public static int[][] base;
public static int[][] find(long num){ //행렬 찾기
if(num == 1){
return base;
}
return calc(find(num/2),find(num-num/2));
}
public static int[][] calc(int[][] arr1, int[][] arr2){ //행렬 곱셉 함수
int[][] result = new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int temp = 0;
for(int k=0;k<N;k++){
temp += arr1[i][k]*arr2[k][j];
}
result[i][j] = temp%1000;
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
base = new int[N][N];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
base[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] result = find(B);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.printf(result[i][j]+" ");
}
System.out.println();
}
}
}얼레?
이랬더니 Number Format 에러가 떴다.
생전 보지도 못했던 에러였는데
알고보니 문자열에서 숫자로 변환될 때 발생한다고 한다.
근데 아무리 봐도 내 코드에서 숫자로 변환하는거에는 문제가 없는데?
백준 오랜만에 풀었더니 고장났나? 라는 생각을 했다.
근데 알고보니 B의 범위가 1000억이라는 것을 간과했다.
그래서 B를 Long으로 변경해주었다.
수정 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static long B;
public static int[][] base;
public static int[][] find(long num){
if(num == 1){
return base;
}
return calc(find(num/2),find(num-num/2));
}
public static int[][] calc(int[][] arr1, int[][] arr2){
int[][] result = new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int temp = 0;
for(int k=0;k<N;k++){
temp += arr1[i][k]*arr2[k][j];
}
result[i][j] = temp%1000;
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Long.parseLong(st.nextToken());
base = new int[N][N];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
base[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] result = find(B);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.printf(result[i][j]+" ");
}
System.out.println();
}
}
}얼레?
이번엔 시간초과가 났다.
어느정도 예상은 했는데 제출과 동시에 시간초과가 나서 살짝 당황했다.
이거는 알고리즘 수업시간에도 배웠듯이 분할정복법의 단점인 같은 계산을 반복하는 것에서 생긴 것이다.
public static int[][] find(long num){
if(num == 1){
return base;
}
return calc(find(num/2),find(num-num/2));
}위의 코드에서 find()함수가 불필요하게 많이 호출되는 것이다.
이걸 해결하기 위해 미리 find(num/2)를 계산해두어 여러번 계산하지 않도록 만들어 준다.
수정 코드2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static long B;
public static int[][] base;
public static int[][] find(long num){
if(num == 1){
return base;
}
int[][] save = find(num/2); //미리 계산해서 저장
if(num%2==1){ //현재가 홀수번째라면
return calc(calc(save,save),base);
}
else{
return calc(save,save);
}
}
public static int[][] calc(int[][] arr1, int[][] arr2){
int[][] result = new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int temp = 0;
for(int k=0;k<N;k++){
temp += arr1[i][k]*arr2[k][j];
}
result[i][j] = temp%1000;
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Long.parseLong(st.nextToken());
base = new int[N][N];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
base[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] result = find(B);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.printf(result[i][j]+" ");
}
System.out.println();
}
}
}얼레?
이번엔 채점이 잘 되다가 80%에서 틀렸다고 뜬다..
무엇이 문제일까??
만약 입력이 아래와 같이 주어진다고 생각하자.
2 1
1000 1000
1000 1000그럼 위의 코드에서는 아래와 같은 출력이 나온다.
1000 1000
1000 1000그렇지만 정답은 1000으로 나누어줘야 하기 때문에
0 0
0 0위와 같이 나와야 한다.
그래서 초기 행렬을 입력받는 과정에서 1000을 나눠주어 해당 문제를 해결할 수 있었다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static long B;
public static int[][] base;
public static int[][] find(long num){
if(num == 1){
return base;
}
int[][] save = find(num/2);
if(num%2==1){
return calc(calc(save,save),base);
}
else{
return calc(save,save);
}
}
public static int[][] calc(int[][] arr1, int[][] arr2){
int[][] result = new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
int temp = 0;
for(int k=0;k<N;k++){
temp += arr1[i][k]*arr2[k][j];
}
result[i][j] = temp%1000;
}
}
return result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Long.parseLong(st.nextToken());
base = new int[N][N];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++){
base[i][j] = Integer.parseInt(st.nextToken())%1000; //입력에서 1000 나눠주기
}
}
int[][] result = find(B);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.printf(result[i][j]+" ");
}
System.out.println();
}
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.