[백준 17626] Four Squares (JAVA)

백준 17626번 문제 - Four Squares

17626번: Four Squares

---

문제 분석 

 

 

 

• 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다.
  • 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현
• 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
• 입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

---

해결 포인트

 

• DP로 풀이
• 시간은 0.5초뿐 !
• 1번 풀이 : DP를 제곱수의 합으로 설정 → 하지만 시간 초과
  • dp[1]: 제곱 수 하나로 구할 수 있는 값 : 제곱 값 ! → N에 제곱근을 int형변환 시킨 것까지만 구하기
    dp[n].add(dp[n-i]에 들어있는 수 + dp[i]에 들어있는 수)
  • 이렇게 구하다가 dp[n]에 추가되는 숫자가 N이면 n이 정답
• 2번 풀이 : 1부터 N까지 dp구하기 (dp[n] = dp[n-i] + dp[i] 중 가장 작은 값) → 하지만 시간 초과
• 3번 풀이 : 1부터 N까지 dp구하기 → 성공
  •  dp[n] = dp[n-i*i] 중 가장 작은 값 + 1 
  • n 보다 작은 모든 제곱수 들 중 n - (제곱수)를 한 해 중 가장 작은 해에 1을 더한 값
    

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개

---

코드

 

import java.io.*;
import java.util.*;

public class Main {
    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());

        int [] dp = new int[N+1];
        dp[1] = 1;

        for (int i = 2; i <= N; i++) {
            int min = 999999;

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

        bw.write(dp[N]+"\n");
        bw.flush();
        bw.close();
    }
}