제곱수의 합 (백준 1699번) [JAVA]

 

 결과 문제 번호에 문제 링크 있습니다!

 

문제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128 MB	20260	8357	6157	41.082%

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

 

풀이

재귀 형식으로 일단 풀었는데, $n^2$ < N인 최대의 n을 먼저 구하고,
N에서 n~1 까지 N -$n^2$ 한 값을 계속 계산해줘서 최소 count 찾아게 풀었다

 

코드

import java.io.IOException;
public class Main {
	static int ans = 9999;
	public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		//N입력
		int N = Integer.parseInt(br.readLine().trim());
		int n = (int)Math.sqrt(N);
		findSquare(N,0);
		System.out.println(ans);		
	}
	public static void findSquare(int N,int count) {
		//이미 현재 최소 경우의 수를 넘었으면 더 할 필요가 없음.
		if(count >= ans) {
			return;
		}	
		//끝까지 다 분해했는데, ans보다 작으면 새 값 넣기.
		if(N == 0) {
			ans = count;
		}	
		//n^2 < N인 가장 작은 n
		int n = (int)Math.sqrt(N);
		for(int i=n; i>0; i--) {
            //N - n*n 해가면서 재귀호출
			findSquare(N-i*i,count+1);
		}
	}
}

 

결과

아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출 시간
howtolivelikehuman	1699	맞았습니다!!	12944KB	1608ms	Java	982B	3달 전

 

복기

재귀적으로 풀었을때, for문에서 N의 제곱근인 $\sqrt{N}$ 번 $\sqrt{\sqrt{N}}$ 을 소환하는 형식이 꼬리에 꼬리를 물고 갔다.
하지만 이 문제를 동적 프로그래밍으로 현명하게 풀 수 있었다 (4811 알약)
동적 프로그래밍 은 큰 문제를 작은 문제로 나누어서 풀때(분할정복) 작은 문제들 중 같은 문제를 반복해서 푸는 경우가 생기는데, 이때 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이다.
배열 d[]의 항들에 1로만 제곱근을 채웠을때의 값 (= i)으로 초기화 한 다음, i보다 작은 j* j로 뺏을때의 값들을 저장해 가면서 최소값을 찾는 것이다.

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int i, j, n = sc.nextInt(), d[] = new int[n+1];
		for(i=1;i<=n;i++) d[i] = i;
		for(i=2;i<=n;i++)
			for(j=2;j*j<=i;j++)
				d[i] = Math.min(d[i], d[i-j*j]+1);
		System.out.println(d[n]);
		sc.close();
	}
}

 

아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출 시간
howtolivelikehuman	1699	맞았습니다!!	14928KB	172ms	Java	329B	3달 전

확실히 시간이 많이 단축되었다. 이때의 시간복잡도는 $O(N)$이다