Codeforces Round #589 (Div. 2)

코드 포스 참여 후기

 

평소 코드포스 사이트는 알고 있었지만 바쁜 핑계를 대면서 참가하지 않았다. 같이 인턴을 한 친구가 코드포스를 하자고 해서 Round 589에 처음 참여하였다!! 또한, 요즘 코딩테스트를 진행하면서 시간을 두고 알고리즘 문제 푸는 것이 실력향상에 많은 도움이 된다고 생각하여 참여하게 되었다. 아쉽게도... 1번과 2번 두 문제 밖에 풀지 못했다. 다만, 대회 후에 오픈 카톡방을 통해서 3번의 아이디어를 얻었고 하나의 배움을 얻게 되었다.

 

 

문제 풀이 설명

1번  숫자가 크지 않았기 때문에 전수조사하였다. 정수 l과 r 사이의 모든 수에 대해 자리의 수를 조사하는 방식으로 풀었다.

 

2번 map에 연속적으로 채워진 것은 1, 이후에 1칸은 -1로 표시하여 full과 empty를 구분한다. 만약 이 과정에서 r과 c가 map의 같은 위치에 설정하려는 값이 다르다면 0을 출력한다. 정상적이라면 다 표시한 후에 0인 칸들을 count해주고 2를 곱하면 답이다.

 

3번 3번 문제는 다음과 같은 3가지 단계로 이루어진다고 생각하면 된다. 

 

① 소인수분해, ② n!에서 p의 최대 차수 구하기, ③ Powering number

 

① 소인수분해 :  2부터 시작해서 n의 제곱근까지 나누면서 소수를 찾는다. 남은 수가 n의 제곱근보다 클 경우 에라토스체네스의 체에 의해 소수이기 때문에, 해당 소수도 포함시킨다.

 

② n!에서 p의 최대 차수 구하기 : p로 n을 나눈 수의 개수 + p^2으로 n을 나눈 수의 개수 + p^3...+ p^4...와 같이 p^k(k = 1, 2, 3, 4, 5...)가 n이 넘지 않을 때까지 진행하면 n!에서 p의 최대 차수를 구할 수 있다.

예를 들어, n이 9이고 p가 3일 경우, p^1일 때는 3, 6, 9이고, p^2일 때는 9이므로 9!에서 p의 최대 차수는 4이다.

 

9와 같이 제곱근으로 이루어진 수들을 중복 처리할 수 있는 알고리즘이라고 생각하면 될 거 같다.

 

③ Powering number : naive하게 구할 경우 O(n)이지만, 분할정복 기법을 이용하여 구하면 O(logn)에 구할 수 있다. 

 

 

점 하나 찍혔는데 즐겁다...

참고자료

https://blog.encrypted.gg/757

[실전 알고리즘] 0x0B강 - 수학