2019 CAL Season 1 #E 풀이

문제 원본 : https://algospot.com/judge/problem/read/PASS486

algospot.com :: PASS486

출처 : 알고리즘 문제 해결 전략

출제자 : 31기 김건형

 

맞은 동아리

: 로고스 / EXE&GAIA / 혜옴 / ATOM

정답 소스코드

풀이법은 다음과 같습니다.

입력되는 최대 범위가 10000000까지이고 시간제한이 4초임을 생각하여 여유롭게 문제를 해결할 수 있습니다.

(문제의 원본은 5초의 제한시간이나, CAL은 문제의 난이도를 높이고자 4초로 조정하였습니다.)

c를 입력받기 전에 1~10000000까지 모든 수의 약수들을 저장하고 시작합니다. (본문에서 int형 배열 arr)

언뜻 보기에는 10000000^2의 2중 for문처럼 보이나 정밀하게 계산해보면 2초 이내에 배열을 완성할 수 있습니다.

배열을 만든 후에는 c의 값에 따라 입력을 받아 조건에 부합하는 값의 개수를 세어주면 됩니다.

최종적으로 최악의 경우에도 4초 이내에 정답을 출력할 수 있습니다.