[JAVA67] 1699. 제곱수의 합

1699. 제곱수의 합 (S2)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	65275	26753	19511	40.058 %

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

 

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

summary

자연수를 제곱수의 합으로 나타낼 때 제곱수의 항 최소 개수 구하기

 

strategy

DP 활용

• 최소 개수 구하기 위해서 제곱수 합의 경우의 수를 체크해야 함
• DP 를 통해서 매 순간 최소 개수를 기록함 (1부터 주어진 숫자 N까지)
• 제곱한 수가 현재 숫자보다 작은 경우만 계산해서 최소값 찾기
  • DP[7] 에서는 1*1 = 1, 2*2 = 4, 3*3 = 9, ... 임으로 1과 2만 따짐 
• 이전에 계산해둔 값은 항상 최소 개수로 이루어진다는 가정하에 진행 
  • DP[7 - 1] + 1 = DP[6] + 1 (이때, DP[6] 은 이미 최소의 경우 수를 구해놓은 상태)

note

• 1 ≤ N ≤ 100,000

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

public class Main {
    static int N;
    static int[] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        DP = new int[N+1];

        DP[1] = 1;
        for(int n = 2; n <= N; n++) {
            int min = 100_000;
            for(int i = (int) Math.sqrt(n); i >= 1; i--) {
                min = Math.min(DP[n - i*i] + 1, min);
            }
            DP[n] = min;
        }

        System.out.println(DP[N]);
    }
}

문제	결과	메모리	시간	언어코드	길이
1699	맞았습니다!!	15028 KB	144 ms	Java 11 / 수정	612 B

 

memo

• 1부터 시작해서 if() break 를 생각했다가 큰 수에 제약을 주고 큰 수 부터 1까지 진행함
• 이중 for 문을 돌려도 10만 * 10만 보다 훨씬 작음