일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 대회
- 서버
- 백엔드
- Django
- BOJ
- Naver boostcourse
- 서블릿
- 4기
- AI Tech
- 프로그래밍
- 파이썬
- P Stage
- 2021 Dev-matching 웹 백엔드 개발자
- AI Tech 4기
- 백준
- 프로그래머스
- 웹
- QNA 봇
- 풀스택
- cs50
- Customer service 구현
- 레벨2
- 웹 프로그래밍
- Naver boostcamp
- 장고
- sts
- boostcourse
- 부스트캠프
- 네이버
- 구현
Archives
- Today
- Total
daniel7481의 개발일지
[BOJ] 10830 행렬 제곱 본문
반응형
[출처: 백준 온라인 저지]
문제
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
입력
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)
둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.
풀이
분할 정복을 이용한 거듭제곱 문제는 몇 개 풀어봤는데, 행렬을 거듭제곱하는 문제는 처음이었기에 겁이 나긴 했다. 일단 행렬의 곱셈하는 방법은 a(i, j) 요소에 대하여 A*B행렬일 때 A(i, k) * B(k, j) (k는 0부터 A의 열의 개수이다) 이기 때문에 일단 행렬을 곱하는 함수를 구현해냈다. 또한 매번 곱셈이 끝나면 수가 무한으로 커질 수 있기 때문에 1000으로 나눈 나머지 값을 저장하였다. 그 밑으로는 분할 정복을 통해 거듭제곱하는 함수를 구현해냈다. A**n일때 n을 1이 될 때까지 반으로 나눠서 A**(n//2)*A**(n//2)이런식으로 1이 되면 입력으로 주어진 A행렬을 return해주고 그 뒤로 재귀를 통해 제곱을 구하는 방식이다.
import sys
input = lambda: sys.stdin.readline().rstrip()
n, B = map(int, input().split())
A = [list(map(int, input().split()))for _ in range(n)]
def multiply(A, B):
C = [[0 for _ in range(n)]for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
C[i][j] %= 1000
def div_sqrt(a, b):
if b == 1:
return a
k = div_sqrt(a, b//2)
tmp = multiply(k, k)
if b % 2 == 0:
return tmp
else:
return multiply(a, tmp)
print(div_sqrt(A, B))
반응형
'BOJ' 카테고리의 다른 글
[BOJ] 15997 승부예측(카카오 코드 페스티벌 2018 A) (0) | 2021.12.08 |
---|---|
[BOJ] 11559 Puyo Puyo (0) | 2021.12.07 |
[BOJ] 2636/2638 치즈 (0) | 2021.12.05 |
2021.12.05 BOJ 1748 수 이어쓰기 1 (0) | 2021.12.05 |
2021.12.03 BOJ 9935 문자열 폭발 (0) | 2021.12.03 |