Plite
전자오락 공방
Plite
전체 방문자
오늘
어제
  • 분류 전체보기 (274)
    • 프로젝트 (18)
      • 완성 프로젝트 (3)
      • 프로젝트 진행 내역 (15)
    • 공부 및 정리 (241)
      • 백준 코드 (222)
      • C++ (8)
      • DirectX (2)
      • Unreal Engine (6)
      • 프로그래밍 패턴 (3)
    • 기타 (12)
      • 기타 주저리 (10)
    • 게임과 취미 (1)
    • 대문 (1)

블로그 메뉴

  • 홈
  • 프로젝트
  • 취미, 일상
  • 백준 프로필

공지사항

  • [Read Me]
  • 제 블로그에 방문하신 것을 환영합니다.

인기 글

태그

  • 최소 스패닝 트리
  • 브루트포스
  • KMP
  • LCA
  • 수학
  • 우선순위큐
  • 정수론
  • 위상 정렬
  • C++
  • 트라이
  • 큐
  • 분할정복
  • 기하
  • 구현
  • 조합론
  • UC++
  • 동적계획법
  • SCC
  • 백트래킹
  • 누적합
  • 문자열
  • 투포인터
  • 트리
  • 그래프
  • 이분탐색
  • 정렬
  • 백준
  • 스택
  • 세그먼트 트리
  • 유니온 파인드

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Plite

전자오락 공방

[C++]백준 - 10830번 문제
공부 및 정리/백준 코드

[C++]백준 - 10830번 문제

2021. 7. 17. 15:52

10830번: 행렬 제곱 (acmicpc.net)

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

 

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

 

 


 

생각해 볼 점


행렬의 제곱을 함수에서 사용하는 것은 c++ 특성상 이차원 배열보다는 이차원 벡터를 사용하는 것이 낫습니다.

왜냐하면, 함수에서 이차원 배열을 반환하려 노력해봤지만, 원하는만큼 깔끔하게 작성되지 않았습니다.

 

차라리 이차원배열을 typedef를 통해서 하나의 타입으로 지정해버리고, 그에 대한 곱셈 연산자를 오버로딩하여 행렬의 곱셈을 계산하기 편하도록 하였습니다.

 

분할정복을 사용하는 solution 함수에서는, 차수 B에 따라서

 

B가 짝수면, solution(B/2)의 제곱을,

B가 홀수면 solution(B - 1) * solution(1)을 반환합니다.

 

여기서 solution(1)은 입력 받은 행렬과 동일합니다.

 

 

코드


#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int>> matrix;

matrix original;
int N;

//곱셈 연산자 오버로딩
matrix operator * (const matrix &A, const matrix &B) 
{
    matrix ret;
    ret.assign(N, vector<int>(N));
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            for(int k = 0; k < N; k++) ret[i][j] += A[i][k] * B[k][j];
            ret[i][j] = ret[i][j] % 1000;
        }
    }
    return ret;
}

//재귀 함수
matrix solution(long long B)
{
    if(B == 1) return original;
    if(B % 2 == 0)
    {
        matrix temp = solution(B / 2);
        return temp * temp;
    }
    else
    {
        return solution(B - 1) * original;
    }
}

//출력 함수
void print_matrix(matrix M)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            printf("%d ", M[i][j] % 1000);
        }
        printf("\n");
    }
}

int main() 
{
    long long B;
    cin >> N >> B;
    
    original.assign(N, vector<int>(N));
	for(int i = 0; i < N; i++)
	{
	    for(int j = 0; j < N; j ++)
	    {
	        cin >> original[i][j];
	    }
	}
	print_matrix(solution(B));
	return 0;
}

 

그 외


 

저작자표시 (새창열림)

'공부 및 정리 > 백준 코드' 카테고리의 다른 글

[C++]백준 - 1654번 문제  (0) 2021.07.17
[C++]백준 - 11444번 문제  (0) 2021.07.17
[C++]백준 - 1780번 문제  (0) 2021.07.13
[C++]백준 - 2630번 문제  (0) 2021.06.23
[C++]백준 - 2565번 문제  (0) 2021.06.23
    '공부 및 정리/백준 코드' 카테고리의 다른 글
    • [C++]백준 - 1654번 문제
    • [C++]백준 - 11444번 문제
    • [C++]백준 - 1780번 문제
    • [C++]백준 - 2630번 문제
    Plite
    Plite
    개발 일지, 게임 이야기 등을 적어두는 공간입니다.

    티스토리툴바