알고리즘 풀이 - 백준 1699(제곱수의 합, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

 

문제 링크는 여기를 참조

 

문제의 내용을 보려면 아래 더보기 클릭

 

이 문제는 특정 수 N을 제곱수들의 합으로 표현 시, 최소항의 개수를 구하는 문제이다.

 

 

2. 풀이

 

문제를 이해하기 위해 간단히 예시를 들어보자. N=8일 때, 제곱수들로 나타낼 수 있는 경우의 수는 몇 가지일까? 다음과 같다.

$ 8=1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 $
$ 8=2^2 + 1^2 + 1^2 + 1^2 + 1^2 $
$ 8=2^2 + 2^2 $

 

이 문제는 위와 같이 여러 가지 경우의 수에 따라 숫자를 나타낼 수 있을 때, 그 항의 수를 최소로 나타내는 경우를 찾아야 한다. 위의 예시는 2가 될 것이다.

 

이 문제는 DP로 풀 수 있다. 현재 숫자가 N일 때, i의 제곱만큼 빼는 경우를 생각하면 $ N-i^2 $ 가 될 것이다. 이 때, 이전의 수들 중 $ N-i^2 $와 일치하는 수를 찾아 그 수의 제곱수의 합 중 최소항에서 1만 더하면 되기 때문이다.

물론 일부 숫자는 $i^2$로 나타낼 수 있기 때문에 1이 될 수 있다. 하지만 그런 경우를 제외하고는 이전 숫자에서 제곱수를 더한 경우 중 최소의 경우를 찾는 것이 가장 좋다.

 

문제의 정의를 다시 내려보자.
정의 : DP[N] = 숫자 N을 제곱수로 나타내는 항의 최소 개수

 

따라서, 이 문제는 점화식을 다음과 같이 쓸 수 있다. 최소항의 수를 저장한 배열을 DP[]라고 하자.
점화식 : $DP[N] = min\left\{\begin{matrix} DP[N-i^2]+1(1\leqslant i^2< N)\\ 1(i^2\equiv N) \end{matrix}\right.$

위와 같이 이전의 작은 문제를 중복하여 반복하며 그 최적값을 그대로 쓸 수 있으니 DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

 

기저 상태는 1을 제곱수로 나타내는 경우인데 이는 $1=1^2$ 뿐이니 1로 초기화한다.
기저 상태 : DP[1] = 1

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main {
    static int dp[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
	    dp = new int[n+1];
        
        // 반복문을 통해 정답 찾아가기
        for(int i=1; i <= n; i++){
            dp[i] = i; // 기저 상태도 지정
            
            for(int j=1; j*j <= i; j++){
                
                // 만약 n == i^2 이라면 dp[0] = 0이라서 1로 초기화가 되므로 문제 없다.
                if(dp[i] > dp[i-j*j]+1){
                    dp[i] = dp[i-j*j]+1;
                }
            }
        }
        bw.write(String.valueOf(dp[n]));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        dp = new int[n+1]; dp[1] = 1;
        
        topDown(n);
        bw.write(String.valueOf(dp[n]));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식
    public static int topDown(int n){
        // 여기서 반환 조건식을 지정함
        if(dp[n] > 0 || n == 1) return dp[n]; // 값이 있거나 n이 0이면 반환
        
        dp[n] = n; // 초기에는 n으로 초기화
        
        // 재귀를 통해서 값을 구해온다.
        for(int i=1; i*i <= n; i++){
            int temp = topDown(n-(i*i));
            if(temp+1 < dp[n]){
                dp[n] = temp+1;
            }
        }
        return dp[n];
    }
}

Top-Down은 백준 시도 시, 시간이 매우 오래 걸렸다.. 뭐가 문제인지 아직 파악하지 못했다.

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.