[백준] Four Squares JAVA

반응형

728x90

[백준] Four Squares

---

접근

• DP

---

풀이

다시 돌아온 백준 문제다. 이번 문제는 입력받은 숫자를 제곱수의 합으로 표현하되 가장 짧은 표현식에 사용되는 숫자가 몇 개인지 물어보는 문제다. 입력받은 수를 N이라고 할 때 계속 N의 제곱근을 구하여 제곱만큼 N에서 빼주는 방법을 0까지 반복하여도 수식은 얻어지지만 1자리 수에서 1의 제곱이 여러 번 나오는 등 최솟값이 아닌 경우들이 있다.  예를 들어 N=11339인 경우 문제의 만족하는 정답은 105² x 17² x 5² 지만 위의 방식으로 구현할 경우 106² x 10² x 1² x 1² x 1² 으로 더 많은 연산을 소요하게 된다. 그렇기 때문에 또 DP를 사용해 구현해 주어야 한다.

int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;

DP로 사용할 배열을 초기화시켜 준다. 각 숫자마다 최솟값을 구하는 문제이기 때문에 큰 값으로 초기화시켜 주고 0을 만드는 최소 횟수는 0이기 때문에 0번지는 0으로 초기화시켜 준다.

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

제곱수들을 다룰 배열이다. N의 제곱근 보다 큰 수는 필요가 없기 때문에 크기는 N의 제곱근까지이고 각 인덱스는 제곱수로 채워져 있다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j < squares.length; j++) {
		if (squares[j] > i) break;
		dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
	}
}

DP를 계산하는 코드이다. 1부터 N까지 값을 차근차근 계산한다. 루프를 돌면서 자기 자신과 구해지는 값 중 최솟값으로 계속 갱신을 해 나간다. 각 인덱스에는 그 인덱스 값을 표현하기 위한 최소의 개수가 저장된다. dp[i - squares[ j ]] + 1 는 현재 숫자인 i 값에서 제곱수를 빼면 남게 되는 값으로 예를 들어 i가 15고 squares[ j ]가 3의 제곱인 9라면 15 - 9 = 6으로 3의 제곱근 9를 뺀 한 번 + 1과 dp[6]에 이미 6을 만들기 위한 최솟값이 들어 있기 때문에 9라는 3의 제곱을 가지는 경우의 최솟값을 구할 수 있는 것이다.

i = 1
squares[1] = 1
dp[1] = Math.min(dp[1], dp[1 - 1] + 1) = Math.min(dp[1], dp[0] + 1) = Math.min(Integer.MAX_VALUE, 0 + 1) = 1
squares[2] = 4 > 1 -> 루프 종료

i = 2
squares[1] = 1
dp[2] = Math.min(dp[2], dp[2 - 1] + 1) = Math.min(dp[2], dp[1] + 1) = Math.min(Integer.MAX_VALUE, 1 + 1) = 2
squares[2] = 4 > 2 -> 루프 종료

i = 3
squares[1] = 1
dp[3] = Math.min(dp[3], dp[3 - 1] + 1) = Math.min(dp[3], dp[2] + 1) = Math.min(Integer.MAX_VALUE, 2 + 1) = 3
squares[2] = 4 > 3 -> 루프 종료

i = 4
squares[1] = 1
dp[4] = Math.min(dp[4], dp[4 - 1] + 1) = Math.min(dp[4], dp[3] + 1) = Math.min(Integer.MAX_VALUE, 3 + 1) = 4
squares[2] = 4
dp[4] = Math.min(dp[4], dp[4 - 4] + 1) = Math.min(dp[4], dp[0] + 1) = Math.min(4, 0 + 1) = 1
squares[3] = 9 > 4 -> 루프 종료

i = 5
squares[1] = 1
dp[5] = Math.min(dp[5], dp[5 - 1] + 1) = Math.min(dp[5], dp[4] + 1) = Math.min(Integer.MAX_VALUE, 1 + 1) = 2
squares[2] = 4
dp[5] = Math.min(dp[5], dp[5 - 4] + 1) = Math.min(dp[5], dp[1] + 1) = Math.min(2, 1 + 1) = 2
squares[3] = 9 > 5 -> 루프 종료

내부 동작과정을 나타낸 것이다.

i = 26
squares[1] = 1
dp[26] = Math.min(dp[26], dp[26 - 1] + 1) = Math.min(dp[26], dp[25] + 1) = Math.min(4, 1 + 1) = 2

squares[2] = 4
dp[26] = Math.min(dp[26], dp[26 - 4] + 1) = Math.min(dp[26], dp[22] + 1) = Math.min(2, 3 + 1) = 2

squares[3] = 9
dp[26] = Math.min(dp[26], dp[26 - 9] + 1) = Math.min(dp[26], dp[17] + 1) = Math.min(2, 2 + 1) = 2

squares[4] = 16
dp[26] = Math.min(dp[26], dp[26 - 16] + 1) = Math.min(dp[26], dp[10] + 1) = Math.min(2, 2 + 1) = 2

squares[5] = 25
dp[26] = Math.min(dp[26], dp[26 - 25] + 1) = Math.min(dp[26], dp[1] + 1) = Math.min(2, 1 + 1) = 2

26의 경우 25 + 1의 경우가 가장 연산이 적기 때문에 최소 연산수가 2가 되는 것이다.

---

전체 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < squares.length; j++) {
                if (squares[j] > i) break;
                dp[i] = Math.min(dp[i], dp[i - squares[j]] + 1);
            }
        }

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