BAEKJOON : 1699

No. 1699

1. Problem

2. My Solution

• 첫 번째 방법 -> 시간초과
• n 에서 제곱수를 빼고 남은 값을 인덱스로 갖는 dp[i] 리스트를 이용
• dp[i] = min(dp[i], dp[i-j*j]+1)

import sys
import math

n = int(sys.stdin.readline().rstrip())
dp = [9999] * 100001
dp[0]=0
i = 1

while(i <= n):
    sq = int(math.sqrt(i))
    for j in range(1,sq+1):
        dp[i] = min(dp[i], dp[i-j*j]+1)
    i += 1
 
print(dp[n])

• 두 번째 방법
• 시간초과 부분을 해결

import sys
import math

n = int(sys.stdin.readline().rstrip())
dp = [0] * 100001


for i in range(1,100001):
    sq = int(math.sqrt(i))
    result =[]
    for j in range(1,sq+1):
        result.append(dp[i-(j*j)])
    dp[i] = min(result)+1

print(dp[n])

3. Learned

• dp[i] = min(dp[i], dp[i-j*j]+1) 는 min 으로 비교한 뒤 dp[i] 에 대입하는 연산까지 수행 (첫 번째 방법)
• result 리스트에 모두 삽입한 뒤에 한 번의 min 연산으로 최솟값 구함 (두 번째 방법)
• 또는 아래와 같은 방법을 첫 번째 방법에 적용하면 시간 단축

if dp[i] > dp[i - j*j] + 1:
      dp[i] = dp[i - j*j] + 1