백준 12850번
오늘 풀어본 문제는 백준의 12850번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
숭실 대학교 정보 과학관은 유배를 당해서 캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.
(편의 상 문제에서는 위 건물만 등장한다고 가정하자)
한 건물에서 바로 인접한 다른 건물로 이동 하는 데 $1$ 분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 $D$ 분만 산책을 할 것이다. (산책을 시작 한 지 $D$ 분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
입력
$D$ 가 주어진다 $(1 \le D \le 1,000,000,000)$
출력
가능한 경로의 수를 $1,000,000,007$ 로 나눈 나머지를 출력한다.
풀이과정
1번째 시도
문제를 보고 그래프를 인접 행렬로 바꾼 뒤, 제곱을 해서 경로의 개수를 알아내는 방식으로 해결하기로 했다. 제곱을 하는 과정에서 시간 초과를 피하기 위해서 분할 정복을 이용해야 하는데, 이는 내가 이미 만들어둔 행렬 자료구조에 잘 구현되어 있었고, 나머지 연산을 적용할 수 있도록 수정해준 뒤 그대로 사용하였다.
코드는 다음과 같이 작성하였다. 제출할 때는 헤더 파일의 코드를 메인 함수가 있는 파일에 붙여넣은 뒤 제출하였다.
matrix.hpp
#ifndef __MATRIX_HPP__
#define __MATRIX_HPP__
#include <cstdio>
template <typename T>
class Matrix {
private:
size_t row;
size_t column;
T mod;
T** elements;
public:
Matrix(size_t row, size_t column, T mod = 0) : row(row), column(column), mod(mod) {
elements = new T * [row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column]{};
}
}
Matrix(size_t size, bool isIdentity = false, T mod = 0) : row(size), column(size), mod(mod) {
elements = new T * [size];
for (size_t i = 0; i < size; i++) {
elements[i] = new T[size]{};
if (isIdentity) {
elements[i][i] = static_cast<T>(1);
}
}
}
Matrix(const Matrix& other) : row(other.row), column(other.column), mod(other.mod) {
elements = new T * [row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column];
for (size_t j = 0; j < column; j++) {
elements[i][j] = other.elements[i][j];
}
}
}
~Matrix() {
for (size_t i = 0; i < row; i++) {
delete[] elements[i];
}
delete[] elements;
}
T* operator[] (size_t idx) {
return elements[idx];
}
Matrix& operator= (const Matrix& other) {
if (this == &other) {
return *this;
}
for (size_t i = 0; i < row; i++) {
delete[] elements[i];
}
delete[] elements;
row = other.row;
column = other.column;
elements = new T*[row];
for (size_t i = 0; i < row; i++) {
elements[i] = new T[column];
for (size_t j = 0; j < column; j++) {
elements[i][j] = other.elements[i][j];
}
}
return *this;
}
Matrix operator* (const Matrix& other) {
Matrix result(this->row, other.column);
for (size_t i = 0; i < result.row; i++) {
for (size_t j = 0; j < result.column; j++) {
result.elements[i][j] = 0;
for (size_t k = 0; k < this->column; k++) {
T product;
if (mod != 0) {
product = (this->elements[i][k] * other.elements[k][j]) % mod;
}
else {
product = this->elements[i][k] * other.elements[k][j];
}
result.elements[i][j] += product;
if (mod != 0) {
result.elements[i][j] %= mod;
}
}
}
}
return result;
}
Matrix power(size_t exponent) {
Matrix base(*this);
Matrix result(row, true, mod);
while (exponent > 0) {
if (exponent % 2 == 1) {
result = result * base;
}
exponent = exponent / 2;
base = base * base;
}
return result;
}
size_t getRow(void) {
return row;
}
size_t getColumn(void) {
return column;
}
};
#endif // __MATRIX_HPP__
main.cpp
#include <bits/stdc++.h>
#include "matrix.hpp"
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ull D, mod = 1000000007;
cin >> D;
Matrix<ull> matrix(8, false, mod);
// 정보 0: 1, 3
// 전산 1: 0, 2, 3
// 신양 2: 1, 3, 4, 5
// 미래 3: 0, 1, 2, 5
// 진리 4: 2, 5, 6
// 한경 5: 2, 3, 4, 7
// 학생 6: 4, 7
// 형남 7: 5, 6
matrix[0][1] = 1;
matrix[0][3] = 1;
matrix[1][0] = 1;
matrix[1][2] = 1;
matrix[1][3] = 1;
matrix[2][1] = 1;
matrix[2][3] = 1;
matrix[2][4] = 1;
matrix[2][5] = 1;
matrix[3][0] = 1;
matrix[3][1] = 1;
matrix[3][2] = 1;
matrix[3][5] = 1;
matrix[4][2] = 1;
matrix[4][5] = 1;
matrix[4][6] = 1;
matrix[5][2] = 1;
matrix[5][3] = 1;
matrix[5][4] = 1;
matrix[5][7] = 1;
matrix[6][4] = 1;
matrix[6][7] = 1;
matrix[7][5] = 1;
matrix[7][6] = 1;
matrix = matrix.power(D);
cout << matrix[0][0] % mod;
return 0;
}
그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.
마무리
문제를 해결하는 과정에서, 새로운 자료구조가 필요할 때가 오면 항상 정성껏 구현해두는 편이다. 왜냐하면 처음 만들 때 잘 만들어두면 오늘처럼 쉽게 재활용할 수 있기 때문이다.
이번에는 쉽게 행렬 거듭제곱을 수행할 수 있었지만, 나중에 거대한 행렬을 곱해야 해거나 거듭제곱 해야하는 경우가 조금 걱정된다. 지금 구현한 행렬의 곱셈은 시간 복잡도가 $O(n^3)$ 인데, 듣기로는 더 최적의 방식으로 행렬의 곱셈을 수행할 수 있다고 한다. 거꾸로 말하면, 그러한 방식의 행렬의 곱셈을 요구하는 문제가 나올 수도 있다는 뜻 아니겠는가? 그 때가 오면 조금 힘들어질 것 같다…
여담으로, 풀이 과정의 코드 스니펫에도 올려두긴 했지만, 내가 구현한 행렬 자료구조는 내 레포지토리2에서도 확인할 수 있다. 필요한 사람은 참고하길 바란다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/12850
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C++/custom_data_structures/matrix.hpp