[백준 알고리즘] 1699번 제곱수의 합, 파이썬(python)

1699, 제곱수의 합

📁 문제 출처

• https://www.acmicpc.net/problem/1699

 

💡 생각

• 그 항의 최소 개수를 구하는 문제이다.
• n=11이라면 3^2밖에 사용하지 못한다. 그러면 dp에는 [0, 1, 4, 9] 이렇게 제곱수를 저장해주고 [::-1]해준 뒤 n -= arr[i]해주면서 결괏값을 +=1해 주는 아이디어를 떠올렸지만 틀렸다.

 

틀린 코드

n = int(input())

arr = [0]

for i in range(1, n):
    if i ** 2 < n + 1:
        arr.append(i ** 2)
    else:
        break

arr = arr[::-1]
cnt = 0


while True:
    if n == 0:
        break
    for i in range(len(arr)-1):
        if n >= arr[i]:
            n -= arr[i]
            cnt += 1

print(cnt)

• 무조건 큰 수의 제곱수들로만 나타내는 것이 정답이 아니다.

 

🛠 나의 코드

시간 초과

import sys
input = sys.stdin.readline

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n+1):
    dp[i] = i
    for j in range(1, (i//2 +1)):
        if (j * j) > i:
            break
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])

• min함수 사용으로 인해 시간 초과

 

통과

n = int(input())

dp = [i for i in range (n+1)]

for i in range(1, n+1):
    for j in range(1, i):
        if (j * j) > i:
            break
        if dp[i] > dp[i - j * j] + 1:
            dp[i] = dp[i - j * j] + 1

print(dp[n])

• 처음 dp에는 1의 제곱으로 구한 개수를 저장한다.
• dp[i - j * j] + 1에서 +1을 해주는 이유는
  • dp[4] = dp[4 - 2 * 2] + 1 =dp[0] + 1 = 1
  • dp[4]는 2^2이므로 최소항의 개수가 1이다. 따라서 dp[0]의 개수에서 +1을 해줘야 한다.
• dp[i] > dp[i - j * j] + 1은 말 그대로 dp[i]가 dp[i - j * j] + 1보다 크기 때문에 최소항의 개수가 아니다.
• 따라서 dp[i - j * j] + 1로 바꿔줘야 한다.

 

✔️ 배운 점 및 주의할 점

• 수학적 사고
• 다양한 DP유형의 문제 풀기
• 규칙을 찾기까지의 어려움

 

📌 참고한 코드

• https://chanhuiseok.github.io/posts/baek-10/