백준 Java 1699_제곱수의 합

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class Main {
	
	static ArrayList<Integer> numbers = new ArrayList<Integer>();
	static int[] dp = new int[100001];
	
	
	public static void main(String[] args) throws IOException{
		
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		int n = Integer.valueOf(br.readLine());
		
		ans(n);
		bw.write(dp[n] + "\n");
		
		
		bw.flush();
		bw.close();
	}
	
	public static void ans(int n) {
		
		
		dp[1] = 1;
		
		for(int i=2; i<=n; i++) {
			int min=100001;
			
			for(int j=1; j<=(int)i/2; j++) {
				
				if(j*j == i) { 
					min = 1;
					break;
				}
				else{
					min = Math.min(min, dp[j]+dp[i-j]);
				}
				
			}
			dp[i] = min;
		
		}
		
		return;
		
	}

		
}

접근 방법

• 제곱이라는 것을 활용하여 점화식을 구할 수 있었다.dp배열에 i일 때 가질 수 있는 항의 최소 개수를 담는다.dp의 i - j^2 원소에는 j제곱수가 더해지는 것이므로 + 1을 해준다.최소 개수를 구하는 것이므로 기존 원소와 제곱수를 더한 원소의 개수를 비교해 더 낮은 개수를 넣어준다.
• 점화식 : dp[i] = min(dp[i], dp[i-j^2]+1)

참조

https://hidelookit.tistory.com/121