일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- #알고리즘 #백준 #1987 #백준1987 #algorithm #baekjoon #baekjoon1987 #Java
- #알고리즘 #백준 #17140 #백준17140 #algorithm #baekjoon #baekjoon17140 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #문자열압축 #programmers #C++
- 책리뷰
- 스레드 #동시성 #thread #process #
- #알고리즘 #백준 #15684 #백준15684 #algorithm #baekjoon #baekjoon15684 #C++
- 개발서
- #알고리즘 #백준 #15683 #백준15683 #algorithm #baekjoon #baekjoon15683 #C++
- #알고리즘 #백준 #2580 #백준2580 #algorithm #baekjoon #baekjoon2580 #Java
- #알고리즘 #백준 #1793 #백준1793 #algorithm #baekjoon #baekjoon1793 #C++
- #알고리즘 #백준 #14888 #백준14888 #algorithm #baekjoon #baekjoon14888 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #괄호변환 #programmers #C++
- #알고리즘 #백준 #3190 #백준3190 #algorithm #baekjoon #baekjoon3190 #C++
- #알고리즘 #백준 #17837 #백준17837 #algorithm #baekjoon #baekjoon17837 #C++
- #알고리즘 #백준 #5214 #백준5214 #algorithm #baekjoon #baekjoon5214 #C++
- #알고리즘 #백준 #2573 #백준2573 #algorithm #baekjoon #baekjoon2573 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #블록이동하기 #programmers #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #외벽점검 #programmers #C++
- #알고리즘 #백준 #12094 #백준12094 #algorithm #baekjoon #baekjoon12094 #C++
- #알고리즘 #백준 #1260 #백준1260 #algorithm #baekjoon #baekjoon1260 #Java
- #알고리즘 #백준 #2616 #백준2616 #algorithm #baekjoon #baekjoon2616 #Java
- #알고리즘 #백준 #1525 #백준1525 #algorithm #baekjoon #baekjoon1525 #C++
- #알고리즘 #백준 #17406 #백준17406 #algorithm #baekjoon #baekjoon17406 #C++
- 클린코드
- #알고리즘 #백준 #4386 #백준4386 #algorithm #baekjoon #baekjoon4386 #C++
- #알고리즘 #백준 #2352 #백준2352 #algorithm #baekjoon #baekjoon2352 #C++
- CleanCode
- #알고리즘 #백준 #17136 #백준17136 #algorithm #baekjoon #baekjoon17136 #C++
- 개발자취미
- #알고리즘 #백준 #17472 #백준17472 #algorithm #baekjoon #baekjoon17472 #C++
Archives
- Today
- Total
개발자 일기장.
백준 12849. 본대 산책 본문
본대 산책
Problem?
숭실 대학교 정보 과학관은 캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본 대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.
(편의 상 문제에서는 위 건물만 등장한다고 가정하자)
한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
Input
D 가 주어진다 (1 ≤ D ≤ 100,000)
Output
가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.
Solution
인접 행렬 곱을 통해서 값을 구한다.
가정 cal(a, b) : 행렬 계산 함수
a [8][8] : input ans [8][8] : 결과 |
Code
#include <iostream>
using namespace std;
#define MAX 8
long long a[MAX][MAX] = {
{0,1,1,0,0,0,0,0},
{1,0,1,1,0,0,0,0},
{1,1,0,1,1,0,0,0},
{0,1,1,0,1,1,0,0},
{0,0,1,1,0,1,1,0},
{0,0,0,1,1,0,0,1},
{0,0,0,0,1,0,0,1},
{0,0,0,0,0,1,1,0}
};
long long int c[MAX][MAX], ans[MAX][MAX];
// 인접행렬곱
void cal(long long ta[MAX][MAX], long long tb[MAX][MAX]) {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
c[i][j] = 0;
for (int k = 0; k < MAX; k++)
c[i][j] += (ta[i][k] * tb[k][j]);
c[i][j] %= 1000000007;
}
}
for (int i = 0; i < MAX; i++)
for (int j = 0; j < MAX; j++)
ta[i][j] = c[i][j];
}
int main() {
int d;
cin >> d;
for (int i = 0; i < MAX; i++) {
ans[i][i] = 1;
}
while (d > 0) {
if (d % 2 == 1)
cal(ans, a);
cal(a, a);
d /= 2;
}
cout << (ans[0][0] % 1000000007) << "\n";
return 0;
}
옛날에 풀었던 행렬곱 문제와 똑같은 문제라고 생각되었다.
'취업 > Algorithm.' 카테고리의 다른 글
백준 2166. 다각형의 면적 (0) | 2020.03.06 |
---|---|
백준 12852. 1로 만들기 2 (0) | 2020.03.06 |
백준 2096. 내려가기 (0) | 2020.03.03 |
백준 2448. 별 찍기 - 11 (0) | 2020.03.03 |
백준 16953문제. A→B (0) | 2020.03.02 |