[백준 17626번 / Java] Four Squares - DP

문제 링크

Silver 3

 

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

17626번: Four Squares

 

 

 

 

풀이

문제 티어는 낮지만 DP문제라서 냉큼 공부

 

처음에는 아래처럼 해당 idx의 제곱값을 구하여 greedy처럼 풀어내려고 했으나

int[] arr = new int[(int) Math.sqrt(n) + 1];
for (int i = 0; i < arr.length; i ++) {
    arr[i] = i * i;
}

 

모든 상황에 만족하지 못했다.

 

n을 줄여가며 제곱 수가 1밖에 존재하지 않는 4 미만의 수가 됐을 때까지 반복해주는 식을 작성했었는데

내가 세운 식을 바탕으로 12를 풀어내면 3^2 + 3의 값인 4가 나오는데

최적의 해는 2^2를 세 번 더한 3이다.

 

dp배열의 값을 바꾸어주어야만 했고, dp배열의 idx값의 제곱 수를 더하는 최소값을 작성하기로 했다.

 

나열해보면 다음과 같다.

dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 1 .......

 

생각해낸 규칙은 제곱수가 갱신될 때까지는 이전 dp에서 +1을 해 주는 것이었는데

갱신될 때는 무조건 1이다. (4 = 2^2, 9 = 3^2 .....)

어떻게 규칙을 줄 수 있을까 하다가 dp[0]이 0이기 때문에, 거기서 +1을 해주면 어떨까라는 생각을 했고 적용시켜보았다.

 

arr[0] = 0; arr[1] = 1;
for (int i = 2; i < arr.length; i ++) {
    int min = 50001;
    for (int j = 1; j * j <= i; j ++) {
        int idx = i - j * j;
        min = Math.min(min, arr[idx]);
    }
    arr[i] = min + 1;
}

 

작성한 전체 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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[] arr = new int[n + 1];

        arr[0] = 0; arr[1] = 1;
        for (int i = 2; i < arr.length; i ++) {
            int min = 50001;
            for (int j = 1; j * j <= i; j ++) {
                int idx = i - j * j;
                min = Math.min(min, arr[idx]);
            }
            arr[i] = min + 1;
        }

        System.out.println(arr[arr.length - 1]);

    }
}