[BOJ] 백준 2904 수학은 너무 쉬워 (C++)

문제 링크

www.acmicpc.net/problem/2904

2904번: 수학은 너무 쉬워

카테고리

소인수 분해(수학)

문제 풀이

1. 먼저, 소수를 모두 구해 배열에 저장한다. (에라토스테네스의 체)

 

2. cal(num)을 통해 모든 입력 받은 num (총 N개)에 대한 소인수 분해를 진행한다.

    👉  이 결과는 map<int, int> dict[]에 각각 저장한다. (인수, 지수)

    👉 단, 이때 소인수 분해한 모든 값들을 누적해서 map<int, int> mp에 저장한다. (인수, 지수)

 

3. 이제, mp에 저장된 인수들의 지수 값들을 N으로 나누어 최대공약수가 될 수 있는 인수와 지수를 찾는다. 

 

4. 이렇게 최종 계산된 최대 공약수에 따라, dict[]를 조사해 각 num에 대해 필요한 인수의 지수 개수를 카운팅해 더해준다.

      👉  예를 들어, 최대공약수가 4라 2의 지수가 2개 필요하다면 num도 2의 지수가 2개이상으로 맞추려면 몇개가 필요한지 구한다.

      👉  8(2x2x2) -> 0개(3개있으므로) , 6(2x3) -> 이라 2가 1개 더 필요하다.

 

5. 3에서 계산한 최대공약수와, 4에서 카운팅한 값을 출력한다.

주의할 점

* 이게 가능한 이유는 (A / K) , (B x K) 가 동시에 일어나기 때문이다.

      👉 필요한 인수를 얻는 다는 것은 나를 제외한 다른 "num 어디선가" 인수를 가져오는 것이나 마찬가지다. 

 

코드 (C++)

채점 결과

한마디

아이디어만 떠오르면 충분히 쉽게 풀 수 있는 문제다. map을 활용해 보자.  😄