AtCoder Beginner Contest 198

Updated:

A. Div

A와 B가 N개의 서로 다른 사탕을 나누려고 할 때, 가능한 조합의 개수를 구하는 문제이다.

A와 B는 적어도 1개 이상의 사탕을 가져야 하는데 N의 크기가 작기 때문에 이중for문으로 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#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;
  int ans=0;
  for(int i=1;i<n;i++) {
    for(int j=1;j<n;j++) {
      if(i+j==n) ans++;
    }
  }
  cout<<ans;
  return 0;
}

B. Palindrome with leading zeros

$0 ≤ N ≤ 10^9$인 $N$이 주어질 때, 앞에 0을 붙여 팰린드롬으로 만들 수 있는지 확인하는 문제이다.

먼저 뒤에 0의 개수를 세어준다. 똑같은 0의 개수가 앞에도 있어야 팰린드롬을 만들 수 있기 때문이다.

  • 예를들어 1210이라는 N이 주어지면 뒤에 0을 앞에도 하나 붙여준다.

다음 만들어진 수를 뒤집은 후 팰린드롬인지 확인하면 해결 할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#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);
  string s;
  cin>>s;
  int len=s.length();
  int zero=0;
  for(int i=len-1;i>=0;i--) {
    if(s[i]=='0') zero++;
    else break;
  }
  if(zero) {
    reverse(s.begin(),s.end());
    while(zero--) s.push_back('0');
    reverse(s.begin(),s.end());
    string rev=s;
    reverse(rev.begin(),rev.end());
    if(rev==s) {
      cout<<"Yes"<<endl;
      return 0;
    }
    cout<<"No"<<endl;
  }
  else {
    string rev=s;
    reverse(rev.begin(),rev.end());
    if(rev==s) {
      cout<<"Yes"<<endl;
      return 0;
    }
    cout<<"No"<<endl;
  }
  return 0;
}

C. Compass Walking

$1≤R≤10^5$인 $R$과 목적지 $(X,Y)$가 주어질 때, $(0,0)$에서 $(X,Y)$까지의 유클리드 거리를 구한 후, $R$의 길이로 목적지까지 가는데 몇번의 스텝이 필요한지 계산하는 문제이다.

이 문제에서 다음 두 가지 경우를 생각해볼 수 있다.

  • $(X,Y)$가 $R$의 범위 밖에 있는 경우

이 경우에는 R을 반지름으로 하는 원 밖에 목적지가 있는 경우이다.

$R$이 1이고 $(2,2)$로 움직여야 하는 상황에서 다음과 같은 그림을 그릴 수 있다.

이때, 원의 테두리로 움직여야 하므로 빨간색 원 -> 주황색 원 -> 보라색 원의 교점들을 이용해 3번만에 $(2,2)$로 도착할 수 있다.

그림을 다시 보면 반지름 2와 4의 원 사이에 $(2,2)$가 존재하는데 두 번째 원과 세 번째 원 사이의 점들은 3번만에 도착할 수 있다.

즉, $(0,0)$과 $(2,2)$의 유클리드 거리를 $d$라 하면, $\lceil \frac{d}{R} \rceil$이 답이된다.

그림과 같이 첫 번째 원의 테두리를 기준으로 반지름 $R$의 원을 하나 더 그리면 반지름 $R$인 원 내부에 목적지가 있는 모든 경우를 2번만에 도달할 수 있다.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
  double r,x,y;
  cin>>r>>x>>y;
  double len=sqrt(x*x+y*y);
  if(len<r) {
    cout<<2;
    return 0;
  }
  cout<<ceil(len/r);
  return 0;
}

D. Send More Money

주어지는 $S_1, S_2, S_3$ 문자열이 알파벳 소문자로 구성되어 있을 때, 각 소문자가 0부터 9까지의 숫자로 치환이 가능하다.(모든 알파벳은 숫자가 중복되지 않는다)

이때, 숫자로 치환된 $N_1, N_2, N_3$가 $N_1+N_2=N_3$을 만족할 때, 가능한 수를 출력하는 문제이다.

먼저, 문자열 $S_1, S_2, S_3$를 구성하는 알파벳의 수가 10개를 초과한다면 당연히 위의 식을 만족할 수 없다.

총 알파벳의 수가 10개이고 각자 0부터 9까지의 수로 치환이 가능하다. 즉, $10!=3628800$ 번만 반복하기 때문에 완전탐색으로 문제를 해결할 수 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <map>
#include <set>
#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;

map<char,int> m;

int main(){
  ios::sync_with_stdio(0);
  //freopen("input.txt","r",stdin);
  string a,b,c;
  cin>>a>>b>>c;
  set<char> s;
  for(char e : a) s.insert(e);
  for(char e : b) s.insert(e);
  for(char e : c) s.insert(e);
  if(s.size()>10) {
    cout<<"UNSOLVABLE"<<endl;
    return 0;
  }
  vector<int> p={0,1,2,3,4,5,6,7,8,9};
  do{
    int i=0;
    for(char word : s) {
      m[word]=p[i++];
    }
    string a_prime="", b_prime="", c_prime="";
    for(char word : a) a_prime+=m[word]+'0';
    for(char word : b) b_prime+=m[word]+'0';
    for(char word : c) c_prime+=m[word]+'0';
    if(a_prime[0]=='0' || b_prime[0]=='0' || c_prime[0]=='0') continue;
    ll a_ll=stoll(a_prime);
    ll b_ll=stoll(b_prime);
    ll c_ll=stoll(c_prime);
    if(a_ll+b_ll==c_ll) {
      cout<<a_prime<<endl<<b_prime<<endl<<c_prime<<endl;
      return 0;
    }
  }while(next_permutation(p.begin(),p.end()));
  cout<<"UNSOLVABLE"<<endl;
  return 0;
}
  • 숫자를 문자로 치환하는 과정에서 to_string()을 사용했는데 TLE를 발생시키는 것을 확인했다.
  • to_string()은 vsnprintf() 측면에서 구현되었는데 sprintf()자체가 덩치가 커서 실행속도가 느리다고 한다.

Tags:

Categories:

Updated:

Comments