3.1.1. 타임머신 ¶
#include<iostream> #include<vector> #include<utility> using namespace std; int d[501] = {0,}; int check[501] = {0,}; vector<vector<pair<int, int> > > vec; int main(){ vec.resize(501); int n,m; cin>>n>>m; for(int i=0; i<m; i++){ int tmp1, tmp2, tmp3; scanf("%d %d %d", &tmp1, &tmp2, &tmp3); vec[tmp1].push_back(make_pair(tmp2,tmp3)); } d[1] = 0; check[1] = 1; bool update = true; for(int i = 0; i<=n && update; i++){ if(i == n){ cout<<-1 <<endl; return 0; } update = false; for(int j = 1; j<=n; j++){ if(!check[j]){ continue; } for(auto it = vec[j].begin(); it != vec[j].end(); it++){ if( !check[it->first] || d[it->first] > d[j] + it->second){ update = true; check[it->first] = 1; d[it->first] = d[j] + it->second; } } } } for(int i = 2; i<=n; i++){ if(!check[i]){ cout<<-1<<endl; } else{ cout<<d[i]<<endl; } } }
3.1.2. 오르막 수 ¶
#include<iostream> #include<cstring> using namespace std; int arr[1001][10]; int search(int num, int pri){ if(num == 1){ return 1; } if(arr[num][pri] != -1){ return arr[num][pri]; } int ans = 0; for(int i = 0; i<=pri; i++){ ans += search(num-1, i); ans %= 10007; } arr[num][pri] = ans; return ans; } int main(){ memset(arr,-1,sizeof(arr)); int n; cin >> n; int ans = 0; for(int i = 0; i<10; i++){ ans += search(n,i); ans %= 10007; } cout<< ans <<endl; }
3.1.3. 숨바꼭질2 ¶
#include<iostream> #include<queue> using namespace std; int check[100001] = {0,}; int arr[100001] = {0,}; int main(){ int n, k; cin>>n>>k; queue<int> q; q.push(n); arr[n] = 1; int cnt = 0; while(q.size()){ int si = q.size(); while(si--){ int tmp = q.front(); q.pop(); if(tmp == k){ cout<< cnt <<endl << arr[tmp] <<endl; return 0; } if(tmp + 1 <= 100000){ if(!check[tmp+1]){ arr[tmp+1] = arr[tmp]; check[tmp+1] = cnt; q.push(tmp+1); } else if(check[tmp+1] == cnt){ arr[tmp+1] += arr[tmp]; } } if(tmp -1 >= 0){ if(!check[tmp-1]){ arr[tmp-1] = arr[tmp]; check[tmp-1] = cnt; q.push(tmp-1); } else if(check[tmp-1] == cnt){ arr[tmp-1] += arr[tmp]; } } if(tmp *2 <= 100000){ if(!check[tmp*2]){ arr[tmp*2] = arr[tmp]; check[tmp*2] = cnt; q.push(tmp*2); } else if(check[tmp*2] == cnt){ arr[tmp*2] += arr[tmp]; } } } cnt++; } }
3.1.4. 토마토 ¶
#include<iostream> #include<queue> #include<utility> using namespace std; int arr[1000][1000]; queue<pair<int, int>> q; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int main(){ int left = 0; int n,m; cin>>m >>n; for(int i = 0; i<n; i++){ for(int j = 0; j<m; j++){ scanf("%d", &arr[i][j]); if(!arr[i][j]){ left++; } if(arr[i][j] == 1){ q.push(make_pair(i,j)); } } } bool go = true; int cnt = 0; while(q.size()){ int si = q.size(); while(si--){ auto now = q.front(); q.pop(); for(int i = 0; i<4; i++){ if(now.first+dx[i] < 0 || now.first + dx[i] >= n || now.second+dy[i] <0 || now.second+dy[i] >=m || arr[now.first+dx[i]][now.second+dy[i]] != 0){ continue; } q.push(make_pair(now.first+dx[i],now.second+dy[i])); arr[now.first+dx[i]][now.second+dy[i]] = 1; left--; } } if(left == 0){ cout << cnt+1 <<endl; return 0; } cnt++; } if(left){ cout <<-1 <<endl; } }