AtCoder Beginner Contest 169 후기

 

https://atcoder.jp/contests/abc169

AtCoder Beginner Contest 169 - AtCoder

---

최근에 새로 앳 코더에서 시간이 될 때면 매주마다 대회에 참가하곤 하는데, 문제의 퀄리티도 꽤 괜찮고 무엇보다 생활패턴을 망가뜨리는 원흉(!)인 코드 포스보다 보통 9시에 대회가 시작하는 앳 코더는 CP를 기피하던 저에게 매력적인 선택지였습니다.

비기너 콘테스트는 코드 포스 기준으로 div3정도의 난이도를 가지고 있습니다. 비기너 콘테스트는 이번이 2번째로 참가하는 대회였는데, 첫 대회는 생각보다 너무 쉬워서 당황스러웠을 정도였지만 이번 대회는 그 전 대회가 너무 쉬웠던 탓인지 꽤나 진땀 흘릴 정도였습니다. 

A - Multiplication 1 

생략하겠습니다 ㅎㅎ.

B - Multiplication 2

이래서 C++ 만 할 줄 알면 까다로워질 때가 많습니다. big integer 가 제공되는 python은 난이도가 A번 문제 정도입니다. 하지만 C++ 사용하면 얄짤없이 string을 사용해 큰 수를 구현하거나, 일일이 자릿수를 신경 쓰면서 코딩을 해야 합니다. 후자의 방법은 너무 귀찮아질 것 같아 제 라이브러리에 있는 string_multi함수를 이용했습니다. 

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;

string string_add(string a, string b) 
{

	string new_str = "";
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string long_s;
	string short_s;
	if (a.size() >= b.size()) {
		long_s = a;
		short_s = b;
	}
	else {
		long_s = b;
		short_s = a;
	}
	int carry = 0;
	int dif = long_s.size() - short_s.size();
	for (int i = 0; i < dif; i++)
			short_s += "0";
	for(int i=0;i<long_s.size();i++)
	{
		int hab = stoi(long_s.substr(i, 1)) + stoi(short_s.substr(i, 1)) + carry;
		if (hab > 9) {
			carry = 1;
			hab -= 10;
		}
		else carry = 0;

		new_str += to_string(hab);
	}
	if (carry != 0) new_str += to_string(carry);
	reverse(new_str.begin(), new_str.end());
	return new_str;
}


string string_multi(string a, string b) 
{
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());

	string acc = "0";
	for (int i = 0; i < a.size();i++)
	{
		int carry = 0;
		string gob = "";
		for(int j=0;j<b.size();j++)
		{
			int gob_1 = stoi(a.substr(i, 1)) * stoi(b.substr(j, 1)) + carry;
			gob += to_string(gob_1 % 10);
			carry = gob_1 / 10;
		}
		if (carry != 0) gob += to_string(carry);
		for(int j=0;j<i;j++)
			gob = "0" + gob;
		reverse(gob.begin(), gob.end());
		acc = string_add(acc, gob);
	}
	return acc;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N;
	string now = "1", maxN = "1";
	for (int i = 0; i < 18; i++)maxN += "0";
	cin >> N;
	vector<string>v(N);
	for (auto &i : v)
	{
		cin >> i;
		if (i == "0")
		{
			cout << 0;
			return 0;
		}
	}

	for (auto tmp : v)
	{
		now = string_multi(now, tmp);
		if (now.size() >= 19 && now != maxN)
		{
			cout << -1;
			return 0;
		}
	}

	cout << now;

}

ㄴ입력으로 0이 들어오거나, 현재의 글자 수가 19 이상이면 곧장 종료를 하게 하지 않으면 string_multi의 시간 복잡도 때문에 TLE를 받습니다. string_multi의 시간 복잡도는 저 복잡한 코드같이 매우 높기 때문이죠.

C - Multiplication 3

또 곱셈입니다. B번도 그렇고 C번은 CS지식을 묻는 문제들 같네요. double형보다 더 정밀한 실수형인 long double형을 써야 합니다. 야속하게도 예제문제들이 double형 만으로도 통과하기 때문에 많은 참가자들이 실패 횟수 1은 넘어간 것 같은 문제였습니다.

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;


int main()
{
	ll A;
	long double B;
	cin >> A >> B;
	cout << (ll)((long double)A*B);
}

D - Div Game

문제를 읽고 예제를 푸는 순간 소인수분해임이 자명하다 생각해 코드를 써 내려갔는데 생각보다 코드가 너무 더러워진 문제였습니다. AC를 받긴 했지만 뭔가 꺼림칙한 코드였.. 는데 대회가 끝나고 다른 참가자들의 코드를 훑어보는데 훨씬 깔끔하게 적힌 코드가 있었습니다.

저의 코드는 아주 단순하게 문제를 구현한 방식입니다. 소인수 분해를 하고, 각 소수가 몇 제곱 꼴인지를 map자료구조에 담아 저장하고, 각 제곱 꼴에 맞는 cnt배열을 저장해 모두 더하는 방식입니다.

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
map<int, int>mp;
vector<int>v;

int main()
{
	ll N;
	cin >> N;
	for (ll i = 2; i*i < N; i++)
	{
		while (N%i == 0)
		{
			if (mp.find(i) != mp.end())
				mp[i] += 1;
			else
			{
				mp.insert({ i,1 });
				v.push_back(i);
			}
			N /= i;
		}
	}
	if (N > 1)
	{
		mp.insert({ N,1 });
		v.push_back(N);
	}
	int plus[45] = { 0, };
	int n=2, cnt = 2, value = 1;
	for (int i = 1; i < 45; i++)
	{
		plus[i] = value;
		cnt--;
		if (cnt == 0)
		{
			n += 1;
			cnt = n;
			value++;
		}
	}
	int ans = 0;
	for (auto i : v)
	{
		ans += plus[mp[i]];
	}
	cout << ans;
}

 특히 저 plus배열을 구하는 게 더 깔끔한 방식이 있을 텐데.. 하면서도 시간이 촉박해 조금 더러운 코드가 되었습니다. 

하지만 다음과 같이 더 간단하고 직관적이게 구현할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;
ll n,ans;
int main()
{
	cin>>n;
	for(ll i=2;i<=sqrt(n);i++)
	{
		ll x=i;
		while(n%x==0)
		{
			n/=x;
			x*=i;
			ans++;
		}
		while(n%i==0)n/=i;
	}
	if(n!=1)ans++;
	cout<<ans;
}

E - Count Median

추후 추가 예정..