문제
숭실 대학교 정보 과학관은 캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다.
(편의 상 문제에서는 위 건물만 등장한다고 가정하자)
한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
입력
D 가 주어진다 (1 ≤ D ≤ 100,000)
출력
가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.
|
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
32
33
34
|
#include<iostream>
#include <vector>
#define mod 1000000007
using namespace std;
vector<int> link[8] = {{1, 2},
{0, 3},
{0, 3, 4},
{1, 2, 4, 5},
{2, 3, 5, 6},
{3, 4, 6, 7},
{4, 5, 7},
{5, 6}};
long long dp[2][8];
void doDP() {
for (int i = 0; i < 8; i++) {
dp[1][i] = 0;
for (int j = 0; j < link[i].size(); j++)
dp[1][i] = ((dp[1][i] % mod) + (dp[0][link[i][j]] % mod)) % mod;
}
for (int i = 0; i < 8; i++)
dp[0][i] = dp[1][i];
}
int main() {
int d;
cin >> d;
dp[0][7] = 1;
for (int i = 0; i < d; i++)
doDP();
cout << dp[0][7] << '\n';
return 0;
}
|
cs |
dp문제인데 본문을 해석하는 데 좀 어려움이 있었다. 일단 건물들의 인덱스가 없으니까 그 부분을 먼저 정해주자.
# 0 : 형남공학관
# 1 : 학생회관
# 2 : 진리관
# 3 : 한경직기념관
# 4 : 신앙관
# 5 : 미래관
# 6 : 전산관
# 7 : 정보과학관
다른 dp문제와 마찬가지로 연결된 노드의 값을 더해주며 모듈러 연산을 해주면 된다.
본문에 보면 준영이가 정보 과학관에 박혀 있다고 하니까 정보 과학관을 시작점으로 두고 구해야 한다는 점을 주의하면
될 것 같다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 1744 수 묶기 (0) | 2021.02.06 |
|---|---|
| 백준 온라인 저지 1992 쿼드트리 (0) | 2021.02.05 |
| 백준 온라인 저지 1440 타임머신 (0) | 2021.01.24 |
| 백준 온라인 저지 15486 퇴사 2 (0) | 2021.01.21 |
| 백준 14501 퇴사 (0) | 2021.01.21 |
