[BOJ] 17626 - Four Squares

문제 링크

17626-Four Squares

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

문제 풀이

dp로 푸는 문제
저번달에 푼지 모르고 한번 더 풀었는데
전체적인 흐름은 같지만 내가 보기엔
2번 방식이 좀 더 정석적인거 같다..?
메모리나 속도적인 면에서 조금 더 우수하다

1번

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        System.out.println(dp[n]);
    }
}

2번

import java.util.Scanner;

public class Main {
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        dp = new int[50001];
        for (int i = 1; i * i <= n; i++) {
            dp[i*i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if(dp[i]!= 0) continue;
            makeDp(i);

        }
        System.out.println(dp[n]);
    }

    static void makeDp(int num) {

        for (int i = 1; i * i <= num; i++) {
            if(dp[num] == 0)
                dp[num] = dp[i * i] + dp[num - i * i];
            else dp[num] = Math.min(dp[num], dp[i * i] + dp[num - i * i]);
        }
    }
}