[알고리즘/자바] 백준 1699번 - 제곱수의 합

1699번: 제곱수의 합

 

풀고나면 별거 아닌것 같은데 정답까지 생각이 도달하는데 시간이 꽤 걸렸다. 

 

( 입력이 10 일때 ) dp[10]을 구하기 위해서 이전에 구한 dp[1] ~ dp[9]를 활용할 수 있는 방향으로 머리를 굴렸다. 

 

dp[i] = i를 구하기 위한 최소 항 갯수로 dp를 셋팅하고 아래 처럼 모두 적었다. 

 

위에 작성한 부분을 잘보면 dp[10]을 구하기 위해선 아래와 같은 방법을 사용할 수 있다.

 

이를 코드로 구현하면 아래와 같다. 

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) { // i가 어떤수의 제곱인 경우는 dp가 1이다
					min = 1;
					break;
				}
				else{
					min = Math.min(min, dp[j]+dp[i-j]);
				}
				
			}
			dp[i] = min;
			//System.out.println("dp["+i + "] == " + min);
		}
		
		return;
		
	}

		
}