[Baekjoon] 17626 - Four Squares

📝 문제

 

 

🔑 풀이 과정

· 시간제한이 0.5초로 매우 짧은것과, n이 최대 50,000인것을 보고, 다이나믹 프로그래밍을 사용해서 풀어야겠다고 감은 왔다. 근데 그 이후 풀이는 어떻게 해야할지 몰라서 다른 풀이를 조금씩 참고해가면서 풀었다.

 

· dp배열을 생성하고, dp[i]는 i를 제곱수의 합으로 나타냈을 때 그 항의 최소갯수라고 한다. dp[1] = 1(1^2)은 기본값으로 넣어준다.

 

· i가 2이상 n이하일때, dp[i]는 기본적으로는 dp[i-1] + 1이 된다. (i-1을 만드는 최소항 + 1^2일때) 그러나 i를 제곱수들의 합으로 만들어 준다면 dp[i]가 dp[i-1] + 1보다 더 작아질 수도 있다. 글로 설명하기 말주변이 부족해서, 아래 그림을 참고하면 이해가 될 것이다.

 

· 그림

 

 

 

🔓 답안

import java.io.*;

public class Main {

    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()); //입력

        int[] dp = new int[n+1]; //dp배열 생성
        dp[1] = 1;

        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + 1;

            for(int j = 2; (j * j) <= i; j++){
                dp[i] = Math.min(dp[i], 1 + dp[i - (j*j)]);
            }
        }

        bw.write(dp[n] + "\n");
        bw.flush();
        bw.close();
    }

}

 

 

 

🖤 알고리즘 분류

- 다이나믹 프로그래밍

- 브루트포스 알고리즘