AtCoder Beginner Contest 214

A. New Generation ABC

입력받은 대회 회차에 따라 몇 문제가 출제되었는지 그대로 구현하는 문제이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n; cin>>n;
  if(n>=1 && n<=125) cout<<4;
  else if(n>=126 && n<=211) cout<<6;
  else cout<<8;
  return 0;
}

---

B. How many?

주어진 $S$와 $T$에 대해 $a+b+c≤S$, $a\times b\times c≤T$인 $(a,b,c)$의 개수를 구하는 문제이다.

$0≤S≤100$, $0≤T≤10000$이므로 완전탐색하여 구하면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
const ll MOD=1e9+7;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int s, t;
  cin>>s>>t;
  int ans=0;
  for(int a=0;a<=100;a++) {
    for(int b=0;b<=100;b++) {
      for(int c=0;c<=100;c++) {
        if(a+b+c<=s && a*b*c<=t) ans++;
      }
    }
  }
  cout<<ans;
  return 0;
}

---

C. Distribution

Snuke 0부터 $N$까지 원으로 둘러 앉아있고 각자 $T_i$에 gem 하나를 받을 수 있다. 또한, Snuke $i$는 $S_i$시간에 옆 Snuke로 gem을 넘겨야 한다.

이때, 각 Snuke의 첫 gem을 받는 시간을 모두 구하는 문제이다.

이 문제는 $i$th Snuke가 gem을 받게 되는 경우를 생각해야 한다.

• $T_i$시간에 gem을 받는 경우 = t[i]
• 옆 Snuke로부터 gem을 받는 경우 = ans[i-1]+s[i-1]

즉, ans[i] = min(t[i], ans[i-1]+s[i-1])인 수식을 얻을 수 있다.

이때, $T_i$가 너무 작아 모든 사람에게 영향을 주게 되는 경우 한 바퀴 더 돌려야 최소시간을 계산할 수 있으므로 $2N$번 반복문을 수행해야한다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF=1e9;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n; cin>>n;
  vector<int> s(n), t(n);
  for(auto &it : s) cin>>it;
  for(auto &it : t) cin>>it;
  // i번째 사람은 옆에서 받거나 T시간에 받는다.
  vector<int> v=t;
  for(int i=0;i<2*n;i++) {
    int cur=(i+1)%n;
    int prev=i%n;
    v[cur]=min(v[cur], v[prev]+s[prev]);
  }
  for(auto it : v) cout<<it<<endl;
  return 0;
}