[코딩테스트/ 백준 알고리즘] 17626번 - Four Squares (Java, 자바 풀이)

문제

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

17626번: Four Squares

---

문제 설명

---

문제 풀이

 

i가 제곱 수가 아닐 때

---

i가 제곱수일 때

---

브루트포스

a₁의 값에 따라 결과가 달라지므로 a₁을 감소시키면서 값을 모두 구해본다.

 

memo

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
memo[i]	1	2	3	1	2	3	4	2	1	2	3	3	2	3	3	1	2	2

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        int[] memo = new int[n + 1];
        
        //DP
        memo[1] = 1;
        
        for(int i = 2; i <= n; i++) {
            int a1 = (int)Math.sqrt(i);  //i의 제곱근보다 작거나 같은 자연수
            
            //i가 제곱 수일 때
            if(i == (int)Math.pow(a1, 2)) {
                memo[i] = 1;
            }         
            else {
                int a2 = i - (int) Math.pow(a1, 2);
                while (a1 > 0) {
                    if (memo[a2] != 0) {
                        if(memo[i] == 0)
                            memo[i] = 1 + memo[a2];
                        else
                            memo[i] = Math.min(memo[i], 1 + memo[a2]);
                    }
                    
                    //a₁ 감소
                    a1--;
                    a2 = i - (int) Math.pow(a1, 2);
                }
            }
        }
        
        //출력
        System.out.println(memo[n]);
    }
}