문제 바로가기

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

문제 소개 및 재정의

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%EB%B2%88%ED%98%B8-%EB%AC%B8%EC%A0%9C%EC%9D%B4%EB%A6%84-JAVA

이전의 풀이는 시간복잡도와 공간복잡도가 O(N^(3/2))이다.
근데 O(N)으로 푸는 풀이를 이해해서 글을 쓴다.

어떻게 풀까? - DP

포인트

이전 값을 참고하는 부분이 minis배열인 것에 착안했다.
메모하는 공간은 minis만 있으면 된다.
minis를 최악의 상태로 초기화한다.
N을 1^2의 합으로만 표현할때 항의 수가 최대가 되므로 최악의 상태가 된다.
우리가 구해야 하는 것은 항의 수가 최소가 되는 최선의 상태이므로.
앞에서부터 최선의 값들을 채워나가면 된다.
그럼 앞의 값들을 참조할때, 앞의 값들은 이미 최선의 값들이 선택된 상태이므로 최선의 상태가 유지된다.

코드

package study.week14;

import java.io.*;
import java.util.*;
public class BOJ_1699_제곱수의합2 {
	// 입력고정
	static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
	// 세팅
	static int N;
	static ArrayList<Integer> sub = new ArrayList<>(); // N의 최대값이 10^5이므로 그보다 더 큰 제곱수를 사용할일은 없음.
	static int [] dp;
	static int [] minis;
	static int INF = Integer.MAX_VALUE;
	// 메소드
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		N = Integer.parseInt(input.readLine());
		// 세팅
		//// N이하인 제곱수 구해서 ArrayList에 넣기
		for (int n = 0+1; n < N+1; n++) {
			int nSquare = (int) Math.pow(n, 2);
			if(nSquare <= N) {
				sub.add(nSquare);
			} else {
				break;
			}
		}
		//// dp 테이블 초기화
		dp = new int[N+1];
		
		// 작업
		for (int row = 0+1; row < N+1; row++) { // 0일때는 0으로 초기화해둔다. 자기자신을 더하면서 항의 개수가 1로 초기화되도록 설계.
			int mini = INF;	// 초기에 비교할 대상용.
			for (int col = 0; col < sub.size(); col++) {	// 모든 제곱수를 순회하면서 지금 목표 값에서 해당 제곱수를 뺐을때의 상태를 확인. 그때의 값들 중에서 최소값을 남겨서 저장한다.
				int referIndex = row-sub.get(col);
				if(referIndex<0) { // 참고할 인덱스가 없으면 패스
					continue;
				}
				mini = Math.min(mini, dp[referIndex]+1);	// 최소값 비교후 갱신
			}
			dp[row] = mini;									// 이후 재사용 위해서. 최소값 저장.
		}
		

		// 출력
		System.out.println(dp[N]);
		
		
	}// 메인 종료

}

퍼포먼스

[ 12,364 KB | 140 ms ]

마무리

나름 최적화에 성공했다