#ABC 169 후기
|
처음 해보는 앳코더 대회인데, Beginner 난이도라 그런지 난이도는 A~C까지는 아이디어만 금방 떠올린다면 쉽게 풀 수 있었고, |
#ABC 169 문제
A번 Multiplication 1 - 성공
A x B를 출력하시오.
A와 B의 범위가 1~100의 자연수이므로 그냥 A * B를 계산해서 출력하면 되는 문제였다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void) {
// For fast IO
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int a, b;
cin >> a >> b;
cout << a * b;
return 0;
}B번 Multiplication 2 - 성공
N개의 정수가 주어졌을 때, 각각의 정수를 모두 곱했을 때, 곱한 값을 출력하시오.
만약 그 값이 10^18을 초과할 경우 -1을 대신 출력하시오.
B번 문제의 경우 두 가지를 주의하면 된다고 생각했다.
첫번째는 값에 0이 존재 할 경우, 나머지 값과 상관없이 답은 0이라는 것이고,
두번째는 계산 도중에 값이 long long 범위를 초과할 수 있다는 것이다.
어떻게 구현할까 고민했는데,
1. 처음에 값을 배열에 입력받고, 0이 있는지 확인한다.
2. 0이 존재한다면 답은 0
3. 0이 없다면 배열을 정렬해준다.
4. 이후 작은 원소부터 최대 범위 이하인지 확인하면서 곱해간다.
5. 만약 범위를 초과할 경우 답은 -1
6. 초과하지 않았다면 곱한 값을 출력한다.
위와 같이 구현했다.
주의해야 할 점은 4번에서 범위를 확인할 때,
(현재까지의 곱) * (이번에 곱할 수) < (최대 범위)
로 확인하면, 좌변에서 범위를 초과할 수 있다.
따라서 해당 식을
(이번에 곱할 수) < (최대 범위) / (현재까지의 곱)
으로 표현해서 사용하였다.
아래는 정답코드이다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void) {
// For fast IO
cin.tie(NULL);
ios_base::sync_with_stdio(false);
long double n, cur = 1, maxnum = 1000000000000000000;
vector<long double> nums;
cin >> n;
for(int i = 0; i < n; i++) {
long double num;
cin >> num;
if(num == 0) {
cout << 0;
return 0;
}
nums.push_back(num);
}
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++) {
if(nums[i] <= (maxnum / cur)) {
cur *= nums[i];
} else {
cout << -1;
return 0;
}
}
cout << (long long)cur;
return 0;
}C번 Multiplication 3 - 성공
정수 A와 소수점 둘째자리까지 표현하는 소수 B를 곱한 값을 소수점 이하 값을 제외하고 출력하시오.
두 값을 실수형으로 입력받아서 곱한 후, 출력할 때 정수형으로 출력하면 되는 문제이다.
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void) {
// For fast IO
cin.tie(NULL);
ios_base::sync_with_stdio(false);
long double a, b;
cin >> a >> b;
cout << (ll)(a * b);
return 0;
}D번 Div Game - 성공
정수 N이 주어진다. 정수 z를 선택한다.
z는 N의 약수이며, 소수의 e제곱수이다. (z = p^e)
z는 단 한번만 선택할 수 있으며, 이후 N값을 N/z로 변경한다.
이러한 과정을 반복할 수 있는 최대 횟수를 출력하시오.
처음에 문제를 보자마자, 에라토스테네스의 체로 풀면 되겠거니 싶어서 풀어봤는데,
정수 N의 값이 10^12까지 가능해서, 배열의 최대 크기가 10^6까지 늘어나서 구현에 실패했다.
그래서 일단은 10^5 이하의 소수들을 찾아서, 소수들의 e제곱수로 N을 나눠주는 작업을 진행했다.
이후 만약 남은 N이 1이라면, 현재까지의 카운트를 출력하면 되고,
N이 1보다 크다면, 10^5보다 큰 소수들이 N의 약수에 존재한다고 판단한다.
그래서 (10^5 + 1)부터 10^6 이하까지의 값들이 N을 나누는지 각각 확인하였고,
만약 i가 N의 약수라면, N을 i로 나눌 수 없을 때 까지 나누고, 카운트를 +1 추가한다.
(왜냐하면 소수 i가 세 번 곱해져 있다면, 10^12 범위를 초과하기 때문에, i는 최대 두 번 까지 곱해질 수 있는데, z는 단 한번만 선택할 수 있기 때문에, 결과적으로 한 번만 카운트 할 수 있다.)
이후 10^6까지 반복했는데, N값이 1이 아니라면, 남은 N 자기자신이 10^6 이상의 소수라고 판단한다.
따라서 위의 과정을 진행하고 카운트를 출력하면 된다.
3번정도 틀리고 맞았기 때문에 소스코드가 난잡하지만, 첨부해보면 다음과 같다..
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(void) {
// For fast IO
// cin.tie(NULL);
// ios_base::sync_with_stdio(false);
ll n;
ll cnt = 0;
int arr[100000 + 1] = {0};
vector<ll> pnums;
cin >> n;
// 소수 찾기
for(ll i = 2; i <= 100000 + 1; i++) {
if(arr[i] != 0) continue;
if(n % i == 0) pnums.push_back(i);
for(ll j = 2; i * j <= 100000 + 1; j++) {
arr[i * j] = 1;
}
}
for(int i = 0; i < pnums.size(); i++) {
ll p = pnums[i];
ll cur = p;
while(n % cur == 0) {
n /= cur;
cur *= p;
cnt++;
}
while(n % p == 0) {
n /= p;
}
}
if(1 < n) {
// 100000 + 1 보다 크거나 같은 값으로 곱해져 있음.
for(ll i = 100000 + 1; i < 1000000 + 1 && 1 < n; i++) {
while(n % i == 0) {
n /= i;
cnt++;
}
}
if(1 < n) cnt++; // n은 소수
}
cout << cnt;
return 0;
}