[백준] 제곱수의 합 - 자바

1개로 표현할 수 있는 이 수를 생각하면서!  풀면 된다.

 

2²보다 작은 수

1²으로만 표현할 수 있다.

따라서

 

2²보다 크고 3²보다 작은 수

 1²과 2²으로 표현할 수 있다.

이것을 1²과 2²으로 시작하는 수로 표현한다면

4일 때

이것을 앞의 수와 비교해보면 이렇게 표현할 수 있다.

따라서 더 적은 항의 수를 택하여 이렇게 표현할 수 있다.

 

5일 때

1²과 2²으로 시작하는 수로 표현한다면

이것을 앞의 수와 비교해보면 이렇게 표현할 수 있다.

 

6, 7, 8일 때

따라서 2²보다크고 3²보다 작은 수는 다음과 같이 표현할 수 있다.

3²보다 크고 4²보다 작은 수

1²과 2²과 3²으로 표현할 수 있다.

9일 때

이것을 1²과 2²과 3²으로 시작하는 수로 표현한다면

이것을 앞의 수와 비교해보면 이렇게 표현할 수 있다.

따라서

이런식으로 구할 수 있다.

 

풀이

우선 배열을 선언한 후 dp[1]에 1을 넣어준 후

i = 2부터 dp[i]를 구해줬다.

 

j = 1부터 j²이 i를 넘지 않을 때 까지 for문을 돌렸다.

예시 )

i = 5일 때 j = 1, 2 일 때 j² < i 따라서 1²과 2²으로 시작하는 수로 표현한 후 비교

i = 9일 때 j = 1, 2, 3 일 때 j² < i 따라서 1²과 2²과 3²으로 시작하는 수로 표현한 후 비교

이 중 작은 값을 구해야 하는데,

비교를 위해 j = 1 일 때는 바로 넣고 ( dp[i] = dp[i-1] + 1 )

 j = 1 이 아닐 때는 비교하여 작은 값을 넣었다. ( dp[i] = Math.min(dp[i-j*j] + 1, dp[i]) )

 

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

 

 

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++) {
            for (int j = 1; j*j <= i; j++) {
                if (j == 1) dp[i] = dp[i-1] + 1;
                else dp[i] = Math.min(dp[i-j*j] + 1, dp[i]);
            }
        }

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