FBC #1

dohoon·2021년 3월 9일

백준 그룹 : 빡알수 풀이

목록 보기

6/8

tistory에서 옮겨왔습니다

후기
오늘은 신정이라서 사실 참여하신 분이 두 분 밖에 없다...
그래도 열심히 풀어주신 두 분께 감사를 표한다.
새해에도 다들 열공해서
각자가 원하는 목표를 달성하는 한 해가 되길 바란다.

*오늘 셋에서는 솔직히
B, E가 제일 값진 문제들이였다.

이번 주말은 뭔가 바쁜 것 같으면서도 바쁘지 않게 지나가는 바람에 풀이가 늦어졌다.
벌써 근무 태만인가 두렵지만, 이번 포스팅은 beginner contest라 의욕을 가지고 빠르게 작성할 수 있겠다.
그리고 무엇보다 풀이 작성 속도가 빨라졌다:)

Ⓐ 약수 (1037)

by hgmhc
엄청나게 빠른 속도로 풀어내려 했지만, 실상은 왜맞틀을 엄청나게 외쳤다...
당연히 최소공배수를 떠올리셨을 것이다.

이 때 좋은 함수가 하나 있다. 클래스에 있는 lcm함수이다.
아마 C++2020에서 업데이트가 되었나 그랬던 것으로 알고있다.

A가 1과 N이 아니여야 한다가... 왜맞틀의 요인이 되었다.
lcm을 돌려 나온 결과가 $N$ 이 되기 위해서는 $N=p^k$ 꼴이 되는 수밖에 없다.
따라서 $p^{k-1}$ 도 등장했을 것임이 확실해진다.
이 생각을 통해 $m$ 과 $min\_$ 을 만들어(각각 최대, 최솟값이다) 결과가 겹치게 되는 경우 가장 작은 수인 $p$ 로 나누어 주게 만들었다.

Ⓑ 연구소 (14502)

Ⓒ 조합 0의 개수 (2004)

by hgmhc
수학적 지식이 → 있다면 확신을 가지고 바로 문제 풀이에 임할 수 있다.
ㅤㅤㅤㅤㅤㅤㅤ→ 없다면 살짝의 수학적 감으로 문제 풀이에 임할 수 있다.

long long 범위를 잡지 않으면 틀릴 수 있다.
우선 틀렸다면 그것부터 확인해보시길 바란다.

기본적으로,
$n!=p_1^{e_1}\times p_2^{e_2}\times \cdots$ 로 소인수 분해되었을 때,
$e_i$ 을 구하는 방법을 안다면 이 문제를 풀 수 있음을 알아햐 한다.
왜냐하면 $2$ 의 지수와 $5$ 의 지수 중 더 작은 것을 택해주면 될 것이기 때문이다.

$e_i$ 를 구하기 위해서는, $1, 2, \cdots, n$ 중에 $a$ 의 배수가 몇 개 있을까를 먼저 떠올려보자.
$\left \lfloor \frac {n}{a} \right \rfloor$ 임을 알 수 있다.
그렇다면 $k\times p$ 꼴은 총 $\left \lfloor \frac {n}{p} \right \rfloor$ 개이다.

그런데, $!$ 을 계산하기에는 뭔가 빼먹은 느낌이 있다.
그렇다. $p^\alpha$ 을 인수로 지니는 수들은 더 세주어야 할 것이다.

그러기 위해서는 그저 $p$ 가 있던 자리에 $p^2, p^3, \cdots$ 만 대입해서 싹 다 더해주면 충분할 것이다.

이를 구현한 코드이다. 질문이 있으면 댓글이나 DM!

Ⓓ 집합의 표현 (1717)

by hgmhc
서로소 집합 또는 union-find 등의 이름으로 불리우는 자료구조를 소개하기 위한 문제이다.
만약 이를 사용하지 않고 구현하였다면 꼭 더보기를 통해 확인하길 바란다.
그리고 앞으로는 통상적으로 불리우는 용어인, DSU(Disjoint Set Union)이라는 이름으로 통일할 것이다.

DSU는 상당히 중요한 개념이므로,
다음의 링크를 방문하여 배워보시길 추천드립니다. (갓라이...)
~~물론, 나중에 시간이 된다면 모르고리즘에도 DSU 개념 글을 올려보도록 하겠습니다.~~

확인해보셨다면 다음 코드를 이해하는 것은 어렵지 않을 것입니다.