AtCoder Beginner Contest 169 회고

ABC 169

AtCoder Beginner Contest 169 - AtCoder

A. Multiplication 1

$A, B$가 주어졌을 때, $A*B$를 출력하는 문제입니다.

 

B. Multiplication 2

최대 10만개의 0과 $10^{18}$ 이하의 양의 정수로 이루어진 수열이 주어질 때, 수열에 등장한 수를 모두 곱한 값을 출력하는 문제입니다.

단, 수열의 수를 모두 곱한 값이 $10^{18}$을 넘는다면, $-1$을 출력해야 합니다.

 

수를 모두 곱해서 0이 되는 경우의 예외 처리를 잘 해주면 됩니다. CPP의 경우엔 오버플로우 판단을 따로 해줘야 하지만, Python은 기본적으로 Big Integer을 제공하기 때문에 이용하면 편합니다.

 

C. Multiplication 3

두 수 $A$와 $B$가 주어졌을 때, $A*B$를 구하는 문제입니다. 단, $B$는 소수 2번째 자리까지 주어지는 수입니다.

단, $A*B$의 결과의 소수 부분은 버림을 해야합니다. $A*(B*100)$을 해서 뒤의 두 자리 수를 지워주면 되는 문제입니다.

 

double이나 float을 사용하는 경우에는 부동소수점 오류로 인해 오차가 발생할 수 있습니다. Python의 Decimal을 사용하면 쉽게 해결할 수 있습니다.

 

D. Div Game

소인수 분해를 한 다음, 각 소인수들을 중복되지 않은 수들의 곱으로 최대한 많이 나누는 문제입니다. 소인수 분해를 진행 한 다음, 문제의 제한이 $10^{12}$이므로, $p^e$꼴의 수가 여러 개 등장합니다. 하지만, 아무리 $p^e$를 크게 한다고 하더라도 $2^{40}$ 정도에서 끝이 납니다.

 

$1=1$, $2=2$, $3=1+2$, $4=1+3$, $5=2+3$, $6=1+2+3$ ... 순으로 계속 나열하다 보면 1부터 X까지 더한 값을 기준으로, 각 수를 최대한 나눌 수 있는 수의 개수가 변한다는것을 알 수 있습니다. 이를 이용해 각 소인수의 $e$를 최대한의 수로 나눠주면 해결할 수 있습니다.

 

저는 소인수 분해할 때 폴라드 로 알고리즘을 사용했지만, $O(\sqrt{n})$의 알고리즘으로도 쉽게 해결할 수 있습니다.

 

E. Count Median

구간이 여러개 주어질 때, 그 구간이 가질 수 있는 중앙값의 개수를 세는 문제입니다. 구간을 시작점, 끝점을 기준으로 정렬한 다음, 중앙에 있는 구간을 이용해 갯수를 세어주면 풀리는 문제입니다.