[JAVA] 백준 q17626 - Four Squares

17626번: Four Squares

---

 

의식의 흐름

dp로 1~n까지 만드는데 필요한 최소 개수 구해보자.

+ 종이에 1~12까지 구할 수 있는 최소 경우의 수를 써보는데 12 = 3^2+1^2+1^2+1^2(4개) / 2^2+2^2+2^2(3개)로 나뉘는 것을 확인하고 무조건 최대 제곱수를 쓰면 틀리겠구나 생각함

 

풀이 과정

1. 자연수(n)을 입력받는다.

2. 1~n까지 만드는데 필요한 제곱수의 최소 개수를 구하여 배열(dp)에 저장한다.

dp[i] = i를 만드는데 필요한 제곱수의 최소 개수

이때, 최대 제곱수를 이용한다고 최소 개수가 되는 것이 아니므로 모든 경우를 구해서 최소 개수를 찾아본다.

for(int j=1;j*j<=i;j++){
	minCnt = Math.min(minCnt, dp[i-j*j]+1);
}

3. dp[n]을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static int n;
    public static int[] dp;

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

        n = Integer.parseInt(br.readLine());

        dp = new int[n+1];
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            int minCnt = Integer.MAX_VALUE;

            for(int j=1;j*j<=i;j++){
                minCnt = Math.min(minCnt, dp[i-j*j]+1);
            }
            dp[i] = minCnt;
        }

        bw.write(Integer.toString(dp[n]));
        bw.flush();
    }
}