[백준,BOJ 1699] 제곱수의 합( JAVA 구현)

-내 생각

  이 문제의 경우 처음에 접근을 1, 2, 3 더하기 문제처럼 접근을 해버려서 오답 처리를 받은 문제였다. 즉, n이 1일 때, 1의 제곱으로 1개, 2일 때 1의 제곱으로 2개, 3일 때 1의 제곱으로 3개... 식으로 증가한다는 규칙을 찾아서 이전 dp배열에서 1개씩 증가하는 식으로 풀었다. 그러나 문제에서도 언급되어 있듯이, 최소항의 개수를 구하기 위해서는 n보다 작은 제곱수부터 구해나가야 최소항을 구할 수 있는 것이다. 해당 규칙을 알고도 다시 시도해서 풀었는데 정답을 받긴 했지만. 아슬아슬하게 통과한 수준이라 다른 분들의 블로그를 참고해야 했다.

 

-해법

  내가 푼 방식은 제곱수와 n이 일치하면 1을 저장하는 방식으로 진행했는데, 그렇게 할 필요가 없이, n값에서 특정 수의 제곱을 빼주면 0이 되므로 dp [0]에 0을 저장해놓음으로써 +1만 해주면 자동적으로 1개가 저장되는 것이 가능하다. 제곱수와 일치하지 않는 경우는 특정 수 - 제곱 수로 해당 수에 저장된 dp배열의 값에서 +1만 해주면 된다.

 

  구체적인 예시를 들어보면, n이 4일 경우, 1부터 4까지 반복을 돌리면, 1일 때, 1의 제곱은 1로 4보다 작으므로 조건에 부합되어 1에 저장되어있는 1 +1로 dp [4] = 2가 된다. 2일 때, 2의 제곱은 4로 일치하므로 dp [4-4]로 0+1이 되어 dp [4]는 0이 된다. 3의 경우는 제곱 수가 9이므로 조건에 부합되지 않아 넘어가게 된다. 

 

  또한 이 문제에서 주의해야 할 점은 n이 12일 경우는, 2의 제곱 3개로 표현이 가능하므로 3의 제곱 + 1의 제곱 3개보다 적은 수의 항으로 표현이 가능하다. (대표적인 반례이다.) 

 

import java.util.*;
import java.math.*;
public class Main {
	
	static int dp[] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		dp = new int[100001];
		dp[1] =1;
		
		for(int i=2;i<=n;i++) {	 // dp 2부터 채우기 시작
			dp[i]=i; //우선 자기자신으로 초기화 해둔다.
			for(int j=1;j*j<=i;j++) { // j는 1부터 제곱 수가 i보다 작을 경우 반복한다.								
				dp[i] = Math.min(dp[i-(j*j)]+1,dp[i]); // 최소항의 개수를 찾기 위해서 저장 된 값과 점화식값을 비교하여 최솟값을 취한다.		
			}
		}
		
		System.out.println(dp[n]);
			
	}
	
}

  아래는 내가 작성한 코드이다.

 

import java.util.*;
import java.math.*;
public class Main {
	
	static long dp[] ;
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		dp = new long[100001];
		dp[1] =1;
	
		for(long i=2;i<=n;i++) {	
			for(long j=1;j<i;j++) {
				long x = i-j; // 최대 제곱 수를 찾기 위한 과정
				long com =x*x;
				if(com==i) dp[(int) i] = 1; // 제곱 수가 일치하면 1을 저장
				else if(com< i) { // 작은 경우는
					if(dp[(int) i]==0) { // 저장된 값이 없으면, 점화식만 수행
						
						dp[(int) i] = dp[(int) (x*x)] + dp[(int) (i-(com))];
					}
                    // 저장된 값이 있을 경우 점화식과 비교
					else dp[(int) i] = Math.min(dp[(int) com] + dp[(int) (i-(com))],dp[(int) i]);
				}
				else continue;
			}

		}
		
		System.out.println(dp[n]);
			
	}
	
}

 

  위의 정답처리가 훨씬 빠르고 메모리 역시 적게 사용한다는 점을 알 수 있다.