[백준] 동적 프로그래밍 - 1699번 제곱수의 합 (Java)

문제링크

1699번: 제곱수의 합

 

접근한 방법

• 동적 프로그래밍

 

---

풀이 방법

• 이 문제를 며칠을 고민했는지 모른다 ㅠㅠ
• 결국, 다른 분들의 블로그 풀이를 보고 겨우.... 이해했다... 이해 잘 된 거겠지...

규칙을 찾기 위해 아래와 같이 나열하고, 그에 따른 점화식을 세워보자.

$a_{n} = min(a_{n- {1}^{2}} + 1, a_{n-{2}^{2}} + 1 , ... , a_{n-{i}^{2}} + 1)$

• ${i}^{2}$ 은 n보다 작은 수

 

$a_{n}$	식	개수	수열
$a_{1}$	${1}^{2}$	1
$a_{2}$	${1}^{2} + {1}^{2}$	2	$a_{2-{1}^{2}}$ + 1 = $a_{1}$ + 1
$a_{3}$	${1}^{2} + {1}^{2} + {1}^{2}$	3	$a_{3-{1}^{2}}$ + 1 = $a_{2}$ + 1
$a_{4}$	${2}^{2}$	1	$a_{4-{2}^{2}}$ + 1 = $a_{0}$ + 1
$a_{5}$	${2}^{2} + {1}^{2}$	2	$a_{5-{2}^{2}}$ + 1 = $a_{1}$ + 1
$a_{6}$	${2}^{2} + {1}^{2} + {1}^{2}$	3	$a_{6-{2}^{2}}$ + 1 = $a_{2}$ + 1
...
$a_{15}$	${3}^{2} + {2}^{2} + {1}^{2} + {1}^{2}$	4	$a_{15-{3}^{2}}$ + 1 = $a_{6}$ + 1
$a_{16}$	${4}^{2}$	1	$a_{16-{4}^{2}}$ + 1 = $a_{16}$ + 1
...
$a_{31}$	${5}^{2} + {2}^{2} + {1}^{1} + {1}^{1}$	4	$a_{31-{5}^{2}}$ + 1 = $a_{6}$ + 1
$a_{32}$	${4}^{2} + {4}^{2}$	2	$a_{32-{4}^{2}}$ + 1 = $a_{16}$ + 1

---

소스코드 작성 방법

• square 배열에 제곱된 값을 초기화 시켜둔다
  그 크기는 n의 최대값 100,000을 넘지 않도록 초기화한다. (316 * 316 = 99,856)
  하지만, 이중 반복문 안에서 j++이 되면 index가 317이 되므로 ArrayIndexOutOfBoundsException 이 발생한다.
  따라서, 배열의 크기는 318로 지정한다.
• a[0]과 a[1]을 초기화한다.
• 반복문을 사용해서 a[i]의 값을 자기 자신으로 초기화해둔다.
• for(int j=1 ...) 반복문에서 이미 저장되어있는 a[i]의 값과
  j++로 인해 저장될 a[i]값을 비교하여 최솟값을 저장한다.

실수한 점

• 처음에는 n보다 작은 제곱 수 중 가장 최대인 값을 기준으로 문제를 풀었다.
  하지만, 32의 경우 'a[25] + a[7]' 보다 'a[16] + a[16]' 일 경우에 최소값을 갖는다.
• for문을 아래 작성한 것과 같이 사용하는 건 상상도 못했다......

 

소스코드

package baekjoon.dp;
import java.io.*;

public class Q_1699_SumOfSquareNumber {
    public static int solution(int n) {
        int[] square = new int[318];

        for(int i=0 ; i<square.length ; i++){
            square[i] = i * i ;
        }

        int[] a = new int[n + 1];
        a[0] = 0;
        a[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            a[i] = i;
            for (int j = 1; square[j] <= i; j++) {
                a[i] = Math.min(a[i], a[i-square[j]]+1);
            }
        }

        return a[n];

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        bw.write(solution(n)+"\n");

        br.close();
        bw.close();
    }
}