Q1699. 제곱수의 합

제곱근의 최소값을 저장하며 나아가는 로직

1. 제곱근을 가지는 수(ex 1, 4, 9, 16)의 최소값은 1이므로, 1로 세팅합니다.

2. 문제에서 "어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다."이므로,

dp [i] = dp[i-j*j] + dp[j*j] 의 로직이 가능합니다.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q1699 { static int[] dp = new int[100001]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.valueOf(st.nextToken()); for (int i = 1; i*i <= num; i++) { dp[i*i] = 1; } for (int i = 1; i <= num; i++) { for (int j = 1; j*j < i; j++) { int tempValue = dp[i - j*j] + dp[j*j]; if (dp[i] == 0 || dp[i] > tempValue) { dp[i] = tempValue; } } } System.out.println(dp[num]); } }