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$이 답이된다.
- $(X,Y)$가 $R$의 범위 안에 있는 경우
그림과 같이 첫 번째 원의 테두리를 기준으로 반지름 $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()자체가 덩치가 커서 실행속도가 느리다고 한다.
Leave a comment