BOJ 12849 - 본대 산책

문제 링크(Link)

---

https://www.acmicpc.net/problem/12849

문제 해결 (Solution)

---

 1. dp[i][j] = i 건물에서 j분 일 때의 경우의 수.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 출발 지점과 도착 지점 모두 "정보과학관"이다.

참고(Reference)

---

 - 

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<iostream>
	#include<cstdio>
	#include<string>
	#include<cstring>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<ctime>
	#include<vector>
	using namespace std;
	#define div 1000000007
	int D;
	vector<int> graph[10];
	long long dp[10][100003];
	long long ans;
	long long go(int n,int t){
	if(t==D){
	if(n==7)
	return 1;
	else
	return 0;
	}
	long long& ret=dp[n][t];
	if(ret!=-1) return ret;
	ret=0;
	for(int i=0;i<graph[n].size();i++){
	int next = graph[n][i];
	ret += go(next,t+1);
	ret%=div;
	}
	return ret%div;
	}
	int main(){
	memset(dp,-1,sizeof(dp));
	cin >> D;
	graph[0].push_back(1),graph[1].push_back(0);
	graph[0].push_back(2),graph[2].push_back(0);
	graph[2].push_back(3),graph[3].push_back(2);
	graph[1].push_back(3),graph[3].push_back(1);
	graph[1].push_back(4),graph[4].push_back(1);
	graph[3].push_back(4),graph[4].push_back(3);
	graph[3].push_back(5),graph[5].push_back(3);
	graph[4].push_back(5),graph[5].push_back(4);
	graph[4].push_back(6),graph[6].push_back(4);
	graph[5].push_back(6),graph[6].push_back(5);
	graph[5].push_back(7),graph[7].push_back(5);
	graph[6].push_back(7),graph[7].push_back(6);
	ans = go(7,0);
	printf("%lld",ans);
	return 0;
	}

view raw BOJ 12849.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.