BAEKJOON_1699) 제곱수의 합

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 다이나믹 프로그래밍 1

1699) 제곱수의 합 (19.03.21) (19.09.29)

* 1,2,3 더하기 문제와 비슷한 문제.
* 위의 코드에서 내부 for문에 비교하는 식 대신 min() 함수를 써서 비교했더니
* 시간이 살짝 더 걸렸다. 코드길이도 더 길었는데, 메모리는 지금꺼보다 더 적었다.

* 마지막에 오는 수를 1,2, ... 주어진 수 num 으로 설정.
* 만약 i가 4일 경우,
* 앞의 1의 제곱이 네 번 더해지므로 arr[4]에 우선 4를 넣어두고,
* j가 1일 때 arr[4-1] = arr[3] 에 1을 더한 수와 비교한다.
* 이건 arr[3]까지의 항의 개수에 1제곱을 더해 항의 개수가 하나 늘어난 것이다.
* j가 2일 때는 arr[4-4] = arr[0] 에 1을 더한 수와 비교한다.
* 이는 arr[0]까지의 항의 개수에 2제곱을 더해 항의 개수가 하나 늘어난 것을 뜻한다.

* 이렇게 j는 j*j 가 i 와 같거나 작을때까지를 구하면 된다.

* 총 n개의 칸을 채우는데, 한 칸을 채울 때 올 수 있는 i의 개수는 루트n이다.
* 마지막 수가 i 제곱이라고 했을 때, 그 전까지의 수는 n-i*i 에 1을 더한 개수들의 최소값이 되고,
* 이 때, i 의 범위는 i*i<=n 이므로 i<=루트n 이다.

* 따라서 시간복잡도는 n*루트n이 된다.