[Java] 백준(실버-3) 17626번 - Four Squares
문제 풀이
이번 문제는 얼핏 보면 그리디 알고리즘과 헷갈리지만, 동적계획법 DP를 이용해 풀어야 한다.
아이디어 도출
처음엔 무작정 제곱수가 큰 것부터 접근해나가려 했지만 N=12일 경우 2^2 + 2^2 + 2^2의 경우도 고려해야 하기 때문에 그리디 알고리즘이 아닌 DP로 풀어야 함을 알게 되었다.
DP를 이용해 부분 문제를 구해주면, 결국 최적해를 구할 수 있게 된다.
어떻게 최적해인 N을 만들기 위한 최소 제곱수의 개수를 구할 수 있을까? 1부터 9까지 최소 제곱수의 개수를 한번 나열하고 살펴보자.
1
2
3
4
5
6
7
8
9
10
1 -> 1^2 -> 1개
2 -> 1^2 + 1^2 -> 2개
3 -> 1^2 + 1^2 + 1^2 -> 3개
4 -> 2^2 -> 1개
5 -> 2^2 + 1^2 -> 2개
6 -> 2^2 + 1^2 + 1^2 -> 3개
7 -> 2^2 + 1^2 + 1^2 + 1^2 -> 4개
8 -> 2^2 + 2^2 -> 2개
9 -> 3^3 -> 1개
...
위처럼 1부터 9까지 살펴보면, N을 만들 수 있는 최소 제곱수의 개수의 패턴을 도출할 수 있다. N보다 작은 제곱수들 중에서 가장 작은 값을 가지는 D[N-제곱수] 값에 1을 더해주면 된다.
즉 이를 통해 도출한 점화식은 다음과 같다.
점화식:
D[i] = min(D[i-j*j])+1
그러면 문제풀이를 위한 아이디어를 그려보자.
- DP 테이블에 D[0]을 0으로, D[1]을 1인 초기값으로 설정한다.
- D[2]부터 D[N]까지 DP 테이블의 값을 채우기 위해 2부터 N까지 순회하며, 각 순회(이중for문)마다 최소가 되는
D[i-j*j]의 값을 D[i]번째에 채운다. - 완전 탐색 종료 후 D[N]번째 값을 출력한다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.*;
class Main {
// DP 테이블 선언
static int[] D;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
int N = Integer.parseInt(br.readLine());
// DP 테이블 초기화
D = new int[N+1];
// 초기값 설정
D[0] = 0;
D[1] = 1;
// DP 함수 실행
DP(N);
// DP 테이블의 N번째 값 출력
bw.write(D[N]+"\n");
}
}
/**
* DP 함수
* 점화식: D[i] = min(D[i-j*j])+1
*/
static void DP(int N) {
// 2부터 N까지 완전탐색으로 순회한다.
for(int i=2; i<=N; i++) {
// 최솟값을 비교하기 위한 변수
int min = Integer.MAX_VALUE;
// 1. i보다 작은 제곱수를 뺄셈한 DP 테이블의 값 중 최솟값을 구한다.
for(int j=1; j*j<=i; j++) {
min = Math.min(min, D[i - j * j]);
}
// 2. D[i]에 1을 더해준다.
D[i] = min + 1;
}
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.