[B17626][Four Squares][java]

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

17626번: Four Squares

 

코드 (DP x)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class B17626_Before {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        for (int i = 1; i <= (int) Math.sqrt(n); i++) { // 한 제곱수를 넣은 리스트
            list1.add((int) Math.pow(i, 2));
        }

        for (int i = 1; i <= (int) Math.sqrt(n); i++) {  // 두 제곱수를 더한 리스트
            for (int j = i; j <= (int) Math.sqrt(n); j++) {
                list2.add((int) (Math.pow(i, 2) + (Math.pow(j, 2))));
            }
        }

        int answer = 4;  // 4로 초기화해놓고
        if (list1.contains(n)) answer = 1;  // list1 에 있으면 한 수로 만들 수 있음
        else if (list2.contains(n)) answer = 2;  // list2 에 있으면 두 수로 만들 수 있음
        else {
            for (int m : list1) {  // list2 를 돌면서
                if (list2.contains(n - m)) { // 만약, n-m 이 list2에 있다면? n-m 과 m 으로 만들 수 있음
                    answer = 3; // m 은 두 수로 이루어져 있기 때문에 3 리턴
                }
            }
        }

        System.out.println(answer);
    }
}

 

 

코드 (DP)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
1 = 1
2 = 1 + 1
3 = 1 + 1 + 1
4 = 2^2
5 = 2^2 + 1
6 = 2^2 + 1 + 1
7 = 2^2 + 1 + 1 + 1
8 = 2^2 + 2^2
9 = 3^3
10 = 3^3 + 1
 */
// 1부터 10까지 규칙을 쓰다 보니까 금방 떠올랐다.
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[n + 1];
        dp[1] = 1;

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

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

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