1699
-
[백준] 1699번 제곱수의 합 (by Python)Programming/Algorithm 2021. 2. 28. 17:19
문제 비슷한 문제인 1, 2, 3 더하기가 있지만 이 문제는 1, 2, 3이 아니라 n과 같거나 작은 모든 제곱수를 다 고려해야한다는 점에서 시간복잡도가 더 높은 문제이다. 그래서 Pypy3 환경에서만 성공할 수 있었다는 아쉬움이 있지만 이 문제에서 요구한 사고력은 내 풀이로도 충분하다고 생각해 더 이상의 최적화를 시도하진 않았다. 풀이 from math import sqrt n = int(input()) sq_num = [i ** 2 for i in range(1, int(sqrt(n) + 1))] dp = [1 if i in sq_num else i for i in range(n + 1)] for i in range(2, n + 1): for j in range(1, int(sqrt(i)) + 1):..