BOJ 백준 1699: 제곱수의 합

Table of contents

들어가며

이 문제는 $O(N * \sqrt{N})$ 시간 복잡도 안에 DP table을 짤 수 있는지 묻는 문제입니다.
그리고 파이썬으로 풀면 약간의 최적화 테크닉도 필요합니다.

풀이 과정

import sys

input = sys.stdin.readline

MAX = int(1e9) + 7
if __name__ == "__main__":
    N = int(input().rstrip())
    dp = [MAX for _ in range(int(1e5) + 1)]
    dp[0] = 0
    for i in range(1, N + 1):
        j = 1
        while True:
            if j * j > N:
                break
            if dp[i - j * j] + 1 < dp[i]:
                dp[i] = dp[i - j * j] + 1
            j += 1
    print(dp[N])

보시면 $\sqrt{N}$ 을 while문을 사용해서 구했습니다.
그러다 보니 if문을 사용해서 매번 체크를 해주다 보니 오버헤드가 발생하였습니다.
그래서 TLE를 받았습니다.

AC 받은 Python 코드

import sys
import math

input = sys.stdin.readline

MAX = int(1e9) + 7
if __name__ == "__main__":
    N = int(input().rstrip())
    dp = [MAX for _ in range(int(1e5) + 1)]
    dp[0] = 0
    for i in range(1, N + 1):
        for j in range(1, int(math.sqrt(N)) + 1):
            if dp[i - j * j] + 1 < dp[i]:
                dp[i] = dp[i - j * j] + 1
    print(dp[N])

math.sqrt() 메서드를 사용하여 TLE를 받지 않고, AC를 받았습니다…! 😆