문제:

크기가 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제곱한 결과를 출력한다.

풀이방법:

B의 최대 크기가 100,000,000,000인 만큼 효율적인 계산 방법이 필요한 문제다. 따라서 다음과 같은 규칙에 의해서 계산을 한다.

 

A^N일 때,

if N이 짝수라면, (A^2)^(N/2)로 수정한다.

if N이 홀수라면, (A^(N-1))*A로 수정하고, A는 answer에 곱한다.

N이 1이 될 때까지 위를 반복하고, 1이면 그 때의 A를 answer에 곱한다.

 

위와 같이 계산을 한다면 지수가 log2단위로 줄어들기 때문에 최대 100,000,000,000번 연산이 최대 36번으로 줄어들게 될 것이다. 

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
n,b = map(int,input().split())
 
def matmul(A,B):
    result = [[0]*len(A) for _ in range(len(B))]
    for i in range(len(A)):
        for j in range(len(B)):
            for k in range(len(A[0])):
                result[i][j] += A[i][k]*B[k][j]
                result[i][j] %= 1000
    return result
            
matrix = []
for _ in range(n):
    matrix.append(list(map(int,input().split())))
    
answer = [[1 if i==else 0 for i in range(n)] for j in range(n)]
 
while b !=1:
    temp = matrix[:]
    if b%2:
        answer = matmul(answer,temp)
        b-=1
    else:
        matrix = matmul(temp,temp)
        b//=2
 
answer = matmul(answer,matrix)
for ans in answer:
    print(*ans)
cs

문제링크:

https://www.acmicpc.net/problem/10830

'Algorithm > Python' 카테고리의 다른 글

[BOJ]5052. 전화번호 목록  (0) 2020.06.23
[BOJ]12865. 평범한 배낭  (0) 2020.06.18
[BOJ]1837. 암호제작  (0) 2020.06.11
[BOJ]9506. 약수들의 합  (0) 2020.06.09
[Programmers]2018 Kakao[1차]추석 트래픽  (0) 2020.05.26

문제:

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1,1 -> 0)

입력:

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

 

출력:

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

 

풀이방법:

 그리디 방법이므로 현재 위치하고 있는 곳에서 A와 B를 비교해서 뒤집을지 결정해주면 된다. 왼쪽 위부터 오른쪽으로 한칸씩 미끄러져 가며 비교를 하고 맨 윗줄을 다 비교하면 그 아랫줄로 내려가서 비교를 해주도록 한다. 이렇게 하면 한 번 그 위치를 기준으로 뒤집은 경우에는 다시 그 칸을 뒤집진 않기 때문에 한 번 뒤집었던 부분을 다시 뒤집을 수 있다는 걱정을 할 필요 없다. 따라서 이렇게 행렬A를 탐색하며 다 뒤집은 다음에 행렬 B와 비교해서 일치한다면 연산의 최솟값을 출력하고 그렇지 않다면 -1을 출력하도록 하였다.

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
31
def change(x,y,A):
    for i in range(3):
        for j in range(3):
            if A[x+i][y+j]==0:
                A[x+i][y+j]=1
            else:
                A[x+i][y+j]=0
    return A
n,m = map(int,input().split())
A=[]
B=[]
for i in range(n):
    A.append(list(map(int,list(input()))))
for i in range(n):
    B.append(list(map(int,list(input()))))
 
count=0
for i in range(n-3+1):
    for j in range(m-3+1):
        if A[i][j]!=B[i][j]:
            A=change(i,j,A)
            count+=1
answer=True
for i in range(n):
    for j in range(m):
        if A[i][j]!=B[i][j]:
            answer=False
if answer:
    print(count)
else:
    print(-1)
cs

문제 링크:

https://www.acmicpc.net/problem/1080

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2022. 사다리  (0) 2019.09.21
[BOJ]1561. 놀이공원  (0) 2019.09.20
[BOJ]10610. 30  (0) 2019.09.18
[BOJ]2875. 대회 or 인턴  (0) 2019.09.17
[BOJ]1744. 수 묶기  (0) 2019.09.16

+ Recent posts