[백준] 1699번:제곱수의 합 (Java 자바)

문제

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

1699번: 제곱수의 합

 

 

풀이 및 소스코드

 

처음에는 아래와 같이 생각했다.

n의 가장 가까운 제곱수 하나와 n에서 제곱수의 값을 뺀 수의 제곱수의 개수를 더하면 된다 ! 라고!

dp[10] 일 때, 10의 가장 가까운 제곱 수인 3^2 하나와 10-9 = 1인 dp[1]의 값을 더하면 될 것이라고 생각했다.

하지만 틀렸습니다 라는 결과가 나왔다. ㅜㅜ

 

또 다시 한 번 생각해봤다.

dp[10] = dp[1]+dp[9] = 2

         = dp[2]+dp[8] = 4

         = dp[3]+dp[7] = 7
         = dp[4]+dp[6] = 4

         = dp[5]+dp[5] = 4  의 최소값인 2가 정답이라는 것이 보였다.

위의 방법을 코드로 나타내면 아래와 같다 !

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

class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] dp = new int[n+1];
		
		dp[1] = 1;
		for(int i=2;i<=n;i++) {
			dp[i] = 10001;
			for(int j=1;j<=i/2;j++) {
				if(j*j==i) {
					dp[i] = 1;
					break;
				}
				dp[i] = Math.min(dp[i], dp[j]+dp[i-j]);
			}
		}
		System.out.println(dp[n]);
	}

}