[BOJ] 12850 본대 산책2 (C/C++)

12850번: 본대 산책2

 

문제

숭실 대학교 정보 과학관은 유배를 당해서  캠퍼스의 길 건너편에 있다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 꽃 이 활짝 핀 본 대를 선망한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.

(편의 상 문제에서는 위 건물만 등장한다고 가정하자)

한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.

입력

D 가 주어진다 (1 ≤ D ≤ 1,000,000,000) 

출력

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

행렬 제곱 문제를 한번 더 풀었다. 이 문제도 풀고보니 행렬 제곱만 사용하면 되는 문제였지만 그걸 아는데 시간이 좀 걸렸다.

 

저번 학기에 이산구조를 재수강했는데, 그때 배웠던 내용이 사용됐다. 인접 행렬에 인접 행렬을 한번 더 곱하면 2번 만에 갈 수 있는 장소가 나오게 된다. 따라서 인접 행렬을 D번 곱하게 되면 출발한 지 D분 이후에 도착할 수 있는 장소들이 나오게 된다. 따라서 인접 행렬의 D제곱을 구하고 그때의 정보과학관의 값을 정답으로 출력하면 된다.

 

인접 행렬을 만들기 위해서 각 장소에 번호를 붙였다. 정보과학관이 4번이므로 마지막에 배열의 (4,4) 값을 확인했다.

번호	장소
0	학생회관
1	진리관
2	신양관
3	전산관
4	정보과학관
5	형남공학관
6	한경직기념관
7	미래관

 

원래는 #define으로 상수를 사용하는 것이랑 const로 선언하는 것이랑 무지성으로 섞어 썼다. 그냥 막연하게 #define은 전처리기가 코드 자체를 바꿔준다고만 알고 있었다. 그런데 갑자기 어떤 것을 사용하느냐에 따라 성능이 달라지나 궁금해져서 찾아보니 두 개가 마냥 똑같은 결과만을 보여주는 것은 아니었다.

 

const를 사용하는 경우엔 변수를 사용하는 것이므로 메모리를 차지하지만 #define은 메모리를 차지하지 않는다. 그 값이 실수형인 경우이거나 선언한 것을 많이 사용하는 경우엔 #define을 사용하는 쪽이 코드 길이가 더 길어지기도 한다. 또 #define을 사용하면 디버깅하기도 좀 불편하다. 연산자 우선순위에 의해서 계산 결과가 다르게 나올 수도 있다. 그래서 결론은 메모리만 충분하다면 코드를 쓰는 입장에선 const를 사용하는 게 훨씬 나을 것 같다.

 

 

	#include <iostream>
	#include <vector>
	using namespace std;
	#define ll long long
	typedef vector<vector<ll>> matrix;
	const int mod = 1000000007;
	int D;
	matrix A = {
	{0, 1, 0, 0, 0, 1, 0, 0},
	{1, 0, 1, 0, 0, 0, 1, 0},
	{0, 1, 0, 1, 0, 0, 1, 1},
	{0, 0, 1, 0, 1, 0, 0, 1},
	{0, 0, 0, 1, 0, 0, 0, 1},
	{1, 0, 0, 0, 0, 0, 1, 0},
	{0, 1, 1, 0, 0, 1, 0, 1},
	{0, 0, 1, 1, 1, 0, 1, 0}
	};
	matrix ans = {
	{1, 0, 0, 0, 0, 0, 0, 0},
	{0, 1, 0, 0, 0, 0, 0, 0},
	{0, 0, 1, 0, 0, 0, 0, 0},
	{0, 0, 0, 1, 0, 0, 0, 0},
	{0, 0, 0, 0, 1, 0, 0, 0},
	{0, 0, 0, 0, 0, 1, 0, 0},
	{0, 0, 0, 0, 0, 0, 1, 0},
	{0, 0, 0, 0, 0, 0, 0, 1}
	};
	matrix operator * (matrix &a, matrix &b) {
	matrix c(8, vector<ll>(8));
	for (int i = 0; i < 8; i++) {
	for (int j = 0; j < 8; j++) {
	for (int k = 0; k < 8; k++) {
	c[i][j] += a[i][k] * b[k][j];
	}
	c[i][j] %= mod;
	}
	}
	return c;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> D;
	while (D > 0) {
	if (D & 1) {
	ans = ans * A;
	}
	A = A * A;
	D = D >> 1;
	}
	cout << ans[4][4] << "\n";
	return 0;
	}

view raw 12850.cpp hosted with ❤ by GitHub

 

 

후기)

벡터랑 연산자 오버로딩은 아직도 손에 잘 익지 않는다. 좀 더 많이 사용해봐야겠다.