[백준(Baekjoon)] 17626. Four Squares (java, 동적계획법(DP))

안녕하세요. 오늘은 백준의 17626. Four Squares 문제를 풀어보겠습니다.

1. 문제 링크

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

2. 문제 풀이

풀이 확인 결과, 다음과 같은 점화식을 도출할 수 있었습니다.

dp[i] = min(dp[i - j x j]) + 1

이 때, i - jxj > 0 이므로, j는 jxj < i인 모든 자연수입니다.

추가로, jxj == i이면, dp[i] 는 반드시 1입니다. jxj != i일 때는 가장 작은 수가 2입니다. 다시 말하면, 2가 하나라도 나올 경우 더이상 for문을 탐색할 필요 없이 종료해도 된다는 뜻입니다.

3. 전체 코드

import java.io.*;

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++) {
            int tmp = 4;
            int limit = (int) Math.sqrt(i);
            
            for(int j = 1; j <= limit; j++) {
                if(limit*limit == i) {
                    tmp = 1;
                    break;
                }
                
                tmp = Math.min(tmp, dp[i-j*j]+1);
                
                if(tmp == 2) {
                    break;
                }
            }
            dp[i] = tmp;
        }
        
        System.out.println(dp[n]);
    }
}

4. 느낀점

동적계획법 풀이는 주어진 문제에서 규칙을 발견하고, 그 규칙을 일반화하는 과정이 제일 중요하다고 느꼈습니다. 다음부터는 하나씩 손으로 써가면서 풀어봐야겠다는 생각이 들었습니다.

[참고한 곳]
https://steady-coding.tistory.com/18