AtCoder Beginner Contest 204

A. Rock-paper-scissors

세 명이서 가위바위보를 진행할 때, 두 사람이 내는 것을 보고 나머지 한 사람이 비기기위헤 무엇을 내야하는지 출력하는 문제이다.

만약 두 사람이 같은 것을 내면 남은 한 사람도 같은 것을 내면 되고, 두 사람이 다른 것을 내면 남은 한 사람은 그 둘과 다른 것을 내면 비길 수 있다.

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

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int x,y;
  cin>>x>>y;
  if(x==y) {
    cout<<x;
    return 0;
  }
  cout<<3-(x+y);
  return 0;
}

---

B. Nuts

$N$개의 나무가 있고 $A_i$개의 열매가 달려 있다.

이 열매들을 수확하기 위해 10개보다 많은 나무에서 10개를 남기고 모두 가져가려고 할 때, 수확한 열매의 총 개수를 계산하는 문제이다.

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

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n;
  cin>>n;
  ll ans=0;
  while(n--) {
    ll a;
    cin>>a;
    if(a>=10) ans+=a-10;
  }
  cout<<ans;
  return 0;
}

---

C. Tour

$N$개의 도시가 있고 $A_i$에서 $B_i$로 이동하는 도로 $M$개가 있다.

반드시 입력된 방향으로 이동할 수 있을 때, 각 도시에서 다른 도시로 이동할 수 있는 모든 경우를 구하는 문제이다. (어떤 도시에 가만히 있는 것도 포함된다.)

어떤 지점에서 DFS나 BFS로 그래프를 탐색한 후 방문한 도시의 수를 누적해서 계산한다.

한번 탐색 시 $O(N+E)$의 시간복잡도를 가지므로 전체 시간 복잡도는 $O(N(N+E))$을 가진다.

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

vector<int> graph[2001];
bool visit[2001];

void dfs(int root) {
  if(visit[root]) return;
  visit[root]=1;
  for(auto node : graph[root]) {
    dfs(node);
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int n,m;
  cin>>n>>m;
  for(int i=0;i<m;i++) {
    int a,b;
    cin>>a>>b;
    graph[a].push_back(b);
  }
  int ans=0;
  for(int i=1;i<=n;i++) {
    memset(visit,0,sizeof(visit));
    dfs(i);
    for(int j=1;j<=n;j++) {
      if(visit[j]) ans++;
    }
  }
  cout<<ans;
  return 0;
}