• 15이원준

# 3. 코드 ¶

## 3.1. 15이원준 ¶

### 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;
}
}
```

# 4. 아이디어 ¶

## 4.1. 15이원준 ¶

• 벨만 포드(이하생략)

### 4.1.2. 오르막 수 ¶

• arr i , j = 숫자의 갯수 i개, 마지막 숫자 j인 수조합의 갯수
• arr i , j = arr i-1, k