[BOJ]1699번: 제곱수의 합(java, c++)

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

1699번: 제곱수의 합

 

방법 1: Top-down 

 

#include <iostream>
#include <cmath>
 
using namespace std;
const int MAX = 100000;
int cnt[MAX + 1];
 
/*
    D[i] : i를 제곱수의 합으로 나타냈을 때, 최소 항의 개수
 
    점화식 : D[i] = min(D[i - j^2]) + 1
*/
int get_min_pow_sum(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (cnt[n] > 0)
    {
        return cnt[n];
    }
 
    int min = n;
    for (int i = 1; i * i <= n; i++)
    {
        if (n - i * i >= 0)
        {
            int tmp = get_min_pow_sum(n - i * i) + 1;
            min = (min > tmp) ? tmp : min;
        }
    }
    return cnt[n] = min;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    get_min_pow_sum(n);
 
    cout << cnt[n];
 
    return 0;
}

 

 

 

방법 2: Bottom-up

import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            int[] arrMin = new int[num + 1];
            
            for (int i = 1; i <= num; i++) {
                arrMin[i] = i;
                
                for (int j = 1; j * j<= i; j++) {
                    
                    if (arrMin[i] > arrMin[i - j * j] + 1) {
                        arrMin[i] = arrMin[i - j * j] + 1;
                    }
                }
            }
 
            System.out.println(arrMin[num]);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 

c++소스

//https://www.acmicpc.net/problem/1699
#include <iostream>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    const int MAX = 100000;
    int cnt[MAX + 1];
 
    /*
        D[i] : i를 제곱수의 합으로 나타냈을 때, 최소 항의 개수
        점화식 : D[i] = min(D[i - j^2]) + 1
    */
    cnt[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt[i] = i;
        for (int j = 1; j * j <= i; j++)
        {
            if (cnt[i] > cnt[i - j * j] + 1)
            {
                cnt[i] = cnt[i - j * j] + 1;
            }
        }
    }
    
    cout << cnt[n];
 
    return 0;
}

 

 

바텀업이 5배이상 빨랐다. 

주어진 수 N 이하의 모든 수를 한번씩 방문 해야 하는 문제라면, N이 크면 클수록

do(1) ~ do(N) 을 모두 돌아야 하는 탑다운 방식의 시간부담이 그만큼 늘어나기 때문으로 보인다.

 

 

TIP1

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

 

32를 예로 들어 생각해보자.

 

 

 

32는 위와같이 2가지 이상의 방법으로 표현할 수 있다.

 

만약 무조건 가장 큰 제곱수부터 시작해서 남은 수를 채워가는 식으로 한다면, 

32 같은 테스트 케이스의 경우에 틀리게 된다. 

for (long i = num / 2; i >= 0; i--) { //( X )
    
    while (i * i <= num) {
        num = num - i * i;
        count++;
    }
    
    if (num == 0) {
        break;
    }
}

처음에 짰다가 틀린 코드...

 

 

그렇기 때문에 이 문제는 다시 한번 생각해보아야 한다.

그렇다.

이 문제는 사실 N이 주어진 게 아니라, 1 ~ N 까지의 수가 주어진 문제인 것이다. 

즉, A[N]을 제곱수의 합으로 표현할 때의 최소개수를 D[N] 이라 하는 수열을 구해야 한다. 

 

 

따라서 1 ≤ K ≤ N 일때,

① D[1] 부터 구해나가야 한다.

② D[K] 일 때, D[1] ~ D[K - 1] 을 반복해서 확인하며

조건문을 충족하는 D[K - 제곱수] + 1 을 찾아야 한다.

for (int j = 1; j * j<= i; j++) {
    
    if (arrMin[i] > arrMin[i - j * j] + 1) {
        arrMin[i] = arrMin[i - j * j] + 1;
    }
}

 

 

D[32] 를 다시 예로 들어보면,

j = 4일 때, D[32] = D[32 - 4 * 4] + 1 = D[16] + 1 = 2  (D[16] =1)

j = 5일 때, D[32] = D[32 - 5 * 5] + 1 = D[7] + 1 =  5  (D[7] = 4)

j = 5일 때 비교되는 수 5는

j = 4일 때 저장된 D[32] 값 2보다 크기 때문에 조건문을 충족하지 못하고 PASS