https://www.acmicpc.net/problem/10830 해당 백준 문제 주소이다.
처음 이 문제를 풀기 위해서 행렬의 곱을 하는 함수를 만든 뒤, 2의 제곱수(2, 4, 8, 16 등) 중에서 입력받은 지수보다 한 단계 작은 제곱수를 구한 뒤 이를 통해 문제를 해결하는 구상을 하였다.
(사실 내가 쓰면서도 이게 무슨 말인가 라는 생각이 든다.. 밑에서 조금 더 자세하게 설명하겠다.)
def matrix_mult(lst1, lst2, leng):
mult_matrix = [[0] * leng for i in range(leng)]
for i in range(leng):
for j in range(leng):
for k in range(leng):
mult_matrix[i][j] += lst1[i][k] * lst2[k][j]
return mult_matrix내가 문제를 풀면서 가장 처음 만들었던 행렬의 곱을 구하는 함수이다. 이는 행렬의 곱을 하는 방법을 아는 사람이라면 바로 알 수 있는 함수일 것이다.
이 함수를 만든 뒤 나는 문제의 조건대로 행렬의 행과 열의 길이를 입력받고 몇 번 제곱할 지 지수의 값을 입력받는 코드를 짰다.
matrixLeng, exponent = input().split()
그러나 문제가 있었다. input() 함수를 통해 입력을 받으면 그 값은 문자열로 입력받게 된다. 그러나 이 변수를 활용하려면 이 변수들의 자료형을 정수형(int)으로 바꿔야 했다.
matrixLeng, exponent = input().split()
matrixLeng = int(matrixLeng)
exponent = int(exponent)이러한 방식으로도 가능했으나 나는 한 줄로 쓰고 싶었기에
matrixLeng, exponent = int(input().split())
이렇게 했으나 아래와 같이 오류가 발생했다.
input().split()를 통해 입력받은 값의 자료형이 List이기 때문에 발생한 오류였다. 오류가 발생했다고 그냥 포기할 내가 아니다. 어떻게든 방법을 찾기 위해 구글링을 열심히 하였다.
그 결과 map()이라는 함수를 이용하면 된다는 사실을 알 게 되었다.
matrixLeng, exponent = map(int, input().split())이러면 오류 없이 잘 처리된다.
그 후 행렬을 생성 후 행렬 값을 입력받는 코드를 만들었다.
matrix = [[0] * matrixLeng for i in range(matrixLeng)]
for i in range(matrixLeng):
matrix[i] = list(map(int, sys.stdin.readline().split()))참고로 map()함수를 통해 입력받을 경우, 자료형이 map 객체이므로 List 자료형으로 형 변환을 해주어야한다. 따라서 list()를 통해 형 변환을 하여 map()함수를 통해 행렬(사실상 이차원 배열)에 값을 입력받는다. (이거 때문에 살짝 애먹었었다.)
그 후 위에서 말헀던 2의 제곱 어쩌구 코드이다. 솔직히 나의 언어 실력이 그리 좋지 못하여 설명을 하기 힘들다. 따라서 코드만 작성하겠다. (참고로 코드를 보면 알 수 있듯이 난 단위 행렬을 이용하였다, I * A(행렬) = A 임을 이용했다.)
matrix_fin = [[0] * matrixLeng for i in range(matrixLeng)]
for i in range(matrixLeng):
matrix_fin[i][i] = 1
while(exponent > 0):
num = 2
matrix_cp = matrix.copy()
while(exponent - num > 0):
num *= 2
matrix_cp = matrix_mult(matrix_cp, matrix_cp, matrixLeng)
matrix_fin = matrix_mult(matrix_fin, matrix_cp, matrixLeng)
exponent -= (num / 2)
for i in matrix_fin:
for j in i:
print(j % 1000, end= " ")
print()이렇게 해서 짠 코드는
이렇게 해서 제출할 경우 답은 정확하게 나오나, 시간이 오래걸려 시간초과가 발생하게 된다. 이를 해결하기 위해 행렬 곱 함수를 아래와 같이 바꿀 경우 시간 초과 문제는 해결된다.
def matrix_mult(lst1, lst2, leng):
mult_matrix = [[0] * leng for i in range(leng)]
for i in range(leng):
for j in range(leng):
for k in range(leng):
mult_matrix[i][j] += lst1[i][k] * lst2[k][j]
for i in range(leng):
for j in range(leng):
mult_matrix[i][j] %= 1000
return mult_matrix