[백준 2986] 파스칼

[ 백준 2986 : 파스칼 ]

파스칼이라는 언어는 몰라서 처음에 뭐지..했던 문제

그래도 몰라도 풀 수 있다.

일단 readin(n) 은 n을 입력받는 문장일 것이다.

그럼 counter := 0 는? 아마 counter = 0 과 같다고 생각하자

for i:=n-1 downto 1 do begin ???? 일단 위에서 := 가 = 과 똑같다고 가정하면

i:=n-1은 i라는 변수가 n-1이라는 것이고 for가 앞에 있으니까 반복문이라는 것까지는 추측가능.
근데 i가 올라가는지 내려가는지 모르겠는데

아마 down이라는 영어를 아시는 분들은 내려간다고 추측했을 것이다.

그리고 n이 i로 나누어 떨어질때까지 counter를 1씩 더해준다.

그럼

N 입력 -> CNT변수 선언 -> 반복( i = N-1 ~ 1 -> cnt++, if(N%i==0) break; ) -> cnt출력

이제 그대로 만들기만 하면되는데
N의 범위가 10억이다... 그럼 최악의 경우?에 10억이 들어버린다.
1초가 FOR문 1억번 연산한다고 생각해보면 무조건 시간초과가 나온다.


그럼 계산이 필요하다는 것을 본능적으로 알 수 있다.

10을 나눴을때 나누어 떨어지는 수는 1,2,5,10이있다. 음..

그럼 28을 보면?

1,2,4,7,14,28 이다.

오 !!

N의 약수 중에서 N을 제외한 가장 큰 수를 구하면된다. 그리고 N에서 그 수를 빼주면? N과의 차이니까 답이된다.

그럼 이제 N의 약수를 구하면되는데
N의 약수를 무턱대고 구하면 시간초과가 난다.

약수나 소수를 구할땐 이 것만 기억하면된다.

A라는 수를 제곱했을때 B를 초과한다면 A이상 부터는 탐색을 할 필요가 없다.

위에서 예를 든 28을 보자

1이 약수가 된 이유는 28을 곱하면 28이 나오기 때문이다.
2가 약수가 된 이유는 14을 곱하면 28이 나오기 때문이다.
4가 약수가 된 이유는 7을 곱하면 28이 나오기 때문이다.

이렇게 본다면 제곱이 28을 넘는 6부터는 6보다 큰 짝이 없다는 소리이다.

그럼 시간복잡도는 최대 10^9에서 sqrt(10^9) 대략 31630 까지 줄어든다.

i=2부터 i*i가 n을 넘지 않을때까지
나누어떨어질때 1과 i와 n/i 의 최대를 갱신해가며 탐색하면 답이나온다.