1R/2016 10 14

오늘의 문제

• [1]
• 수
• [2]
• [3]

참가자

• 15이원준

코드

15이원준

타임머신

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

오르막 수

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

숨바꼭질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++;
  }

}

토마토

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

아이디어

15이원준

타임머신

• 벨만 포드(이하생략)

오르막 수

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