[JAVA] 백준 1699번- 제곱수의 합

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

1699번: 제곱수의 합

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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];

        for(int i=1; i<=n; i++){
            dp[i] = i;
        }

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

 

 

 

이문제는 정말 모르겠어서 다른 블로그들을 참고해서 이해했다.

 

예를 들어 n = 10이라고 하면,

dp[10] = dp[10-1*1], dp[10-2*2], dp[10-3*3]중 최솟값 + 1

로 표현할 수 있다.

 

그렇기 때문에 j*j가 i가 될때까지 이중 for문을 돌며 최솟값을 구한다.

 

 

 

 

 

 

 

참고

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220792326120