17626번 - Four Squares

1️⃣ DP

 

✏️ 풀이 과정

중복조합을 떠올리기 쉽지만 n이 50000일 때 1부터 106까지에서 조합을 고려해야하기 때문에 계산할 수 없을만큼 경우의 수가 많습니다.

 

다이나믹 프로그래밍을 이용한다면 106개에 대해 50000번,(실제로는 1~106의 제곱수부터 시작하기 때문에 이보다 적습니다.) 즉 530만번 가량의 계산으로 시간 초과를 내지 않고 해결할 수 있습니다.

 

아이디어는 Knapsack문제와 똑같이 1부터 1만 있을 때의 50000까지의 조합 수를 배열에 계산하고 2가 추가되었을 때의 최솟값을 다시 각 인덱스의 값을 4이전 인덱스에서 1을 더한 것과 비교하는 식으로 반복하는 것입니다. 주어진 n의 루트값(버림을 통해 정수로 만든)까지 이 과정을 반복하면 배열의 n번째 인덱스에(n+1개 선언한 경우) 답이 저장됩니다.

💻 코드

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int root = (int)Math.sqrt(n);
		int[] dp = new int[n+1];
		int pow;
		for(int i=1;i<=n;i++) {
			dp[i] = i;
		}
		for(int i=2;i<=root;i++) {
			pow = i * i;
			for(int j=pow;j<=n;j++) {
				if(dp[j-pow] + 1 < dp[j]) {
					dp[j] = dp[j-pow] + 1;
				}
			}
		}
		System.out.println(dp[n]);
		br.close();
	}
}