KOMAS

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

다이내믹 프로그래밍을 이용한 문제다.

1, 4, 9, 16.. 과 같은 제곱수를 활용하여 주어진 수 N을 최소한의 개수로 구성하는 것이 답이다.

최적의 값을 idx에 기억해두는 바텀업 방식으로 이중 for문을 사용했다.

해당 문제에서 최적의 값은 최소한의 연산 횟수다.

DP 테이블 초기화

먼저 dp 테이블을 idx는 숫자, value는 최소 연산 횟수로 사용된다.

각 제곱수 idx 는 1로 만들어 주고,

나머지는 min을 알아내야 하니 충분히 큰 값으로 채워놓는다.

첫 for문은 1부터 100_000까지 차례대로 최소 연산을 구하게 된다.

두번째 for문은 최소 연산을 구하기 위해 

j의 제곱이 i 기준 수 보다 크면 의미가 없으므로 continue 하고,

j의 제곱이 i 기준 수보다 작다면 몫과 나머지를 구해서 

나머지 값에 해당되는 idx에 해당되는 값 + 현재 몫으로 이전에 구해둔 값과 비교해서 최적의 값을 구할 수 있다.

바텀업 방식이니

나머지값에 해당되는 idx는 현재 i 위치보다 이전 값일 것이고, 

최적의 값이라는 것이 보장되고 사용하기 무리가 없다.

예전에 풀었던 1463번 1로 만들기 문제와 비슷하다.

코드

import java.io.*;
import java.math.BigInteger; // subtract , multiply, add, mod
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int number = Integer.parseInt(br.readLine());

        // dp 초기화
        int[] dp = new int[100001];
        Arrays.fill(dp, 1000_000);
        dp[0] = 0;
        for(int i = 1 ; i * i<dp.length; i++){
            int powNumber = i * i;
            dp[powNumber] = 1;
        }

        // 1부터 100_000 까지 min을 채워나가기
        for(int i = 1 ; i<dp.length; i++){
            for(int j = 325; j >= 1; j--){
                int jNumber = (int)Math.pow(j, 2);

                if(jNumber > i) // 기준숫자보다 제곱이 커지면 의미가 없으니 넘김
                    continue;

                int divide = i / jNumber;
                int rest = i % jNumber;

                dp[i] = Math.min(dp[i], dp[rest] + divide);
            }
        }
        System.out.println(dp[number]);
    }
}