[백준 - 1699번] 제곱수의 합 - 자바(JAVA) 정리 & 1일 1 DP - 5일차

안녕하세요 이번에 풀어볼 문제는 제곱수의 합입니다. 

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

1699번: 제곱수의 합

어떤식으로 풀었었나?

 

처음에 문제를 풀었을때는 단순하게 N-1의 값 +1 이라고 생각했는데 오류가 있다는 걸 확인했다.

문제를 확인해야할 점은 12인데

12를 그냥 단순하게 n-1로 처리를 하게된다면,  4가 나오게된다. (3*3 +1+1) 11의 최소값 +1 그래서 4!

문제는 최소 경우는 2*2 + 2*2 + 2*2 -> 3 이 나온다. 

 

즉, 이런 방식으로 처리할 수 없다는 것이다. 이 경우마다 제곱수를 빼가면서 이것이 최소값인지 체크를 해야한다.

 

전반적인 것은 https://wootool.tistory.com/102를 그대로 했습니다.

 

 

/** 2020. 2. 23. 오후 10:24:02
 * @author ventulus95
 */
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class No1699_powSum {
	
	static int cache[] = new int [110000];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for(int i=1; i<100001; i++){
			for(int j =1; j*j <=i; j++){
				if(cache[i] > cache[i- j*j]+1 || cache[i] == 0){
					cache[i] = cache[i-j*j]+1; 
				}
			}
		}
		System.out.println(cache[n]);
	}

}