BOJ 17626

Input

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

import sys
input = sys.stdin.readline

n = int(input().strip())

DP

• 최적의 조합을 찾아서 기존의 값을 계속 업데이트 해야 한다는 점
• min 값을 찾아야 한다는 점

이 DP의 조건이었다. 배열을 사용해서 풀어야 하고, 어떻게 접근해야 할지도 감은 잡았는데, brute force로 풀어보려니 안 풀렸었다. 문제 유형을 올바르게 파악할 것..

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

채워야 하는 n 까지 배열을 초기화시키고, i 가 제곱근일 경우 1이 되므로 알맞게 다시 초기화

for i in range(2, n+1):
  if i == int(math.sqrt(i)) ** 2:
    dp[i] = 1

• 다시 2부터 n까지 돌면서 이번엔 값을 알맞게 넣어야 함.

  for i in range(2, n+1):

• 현재 체크하고 있는 i 를 기준으로 더 작은 값 j 를 제곱하여 뺐을 때, 기존의 값*(1로만 더한 개수)* 와 다른 제곱근을 활용한 개수를 비교해서 min 값을 넣는다.

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

Output

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

print(dp[n])