[백준] 17626번 : Four Squares – JAVA [자바]

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

17626번: Four Squares

 

---

• 문제

---

• 문제 풀이

백준 17626번 Four Squares는 DP (다이나믹 프로그래밍)을 이용해서 푸는 문제이다. DP 이론을 조금 더 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

이 문제에서는 자연수 n이 주어지고 n을 표현하는 최소 개수의 제곱수 합을 구하면 된다. 예시를 한 번 보겠다.

n=1 : 1^2 → 1개  

n=2 : 1^2 + 1^2 → 2개

n=3 : 1^2 + 1^2 + 1^2 → 3개

n=4 : 2^2 → 1개

n=5 : 2^2 + 1^2 → 2개

n=6 : 2^2 + 1^2 + 1^2 → 3개

n=7 : 2^2 + 1^2 + 1^2 + 1^2 → 4개

n=8 : 2^2 + 2^2 → 2개

n=9 : 3^3 → 1개

...

이렇게 나열하다 보면 패턴을 찾을 수 있다.

 

dp [i] = Math.min(dp[i], dp[i - j*j]+1);

 

---

• 코드

import java.util.*;
import java.io.*;
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[] dp = new int[50001];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = 5;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

패턴을 찾는데 시간이 조금 걸린 문제였다.