📍 문제 설명
💡 접근
dp[n]을 n까지의 제곱 수 합의 최소 갯수라고 정의해놓는다.
1 ~ n까지 탐색하는데 현재의 숫자에서 제곱수가 구해지는 부분이 있으면 구한다.
13을 예로 들면 제곱수가 1 2 3이 나올텐데
마지막 항이 1의 제곱수일 땐 d[12] + 1(= 13)의 값을 1제곱 13개
마지막 항이 2의 제곱수일 땐 d[9] + 1(= 2)의 값을 (3제곱+2제곱)
마지막 항이 3의 제곱수일 땐 d[4] + 1(= 2)의 값을 (2제곱+3제곱) 구하게 된다.
👩💻 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m, answer;
static int[][] board;
static int[] arr, dp;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static ArrayList<String> list = new ArrayList<>();
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
Main T = new Main();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = kb.nextInt();
//dp[n]은 n 까지의 제곱 수 합의 최소 갯수
dp = new int[n+1];
for(int i = 1; i <= n; i++) {
dp[i] = i;
for(int j = 1; j*j <= i; j++) {
if(dp[i] > dp[i-(j*j)] + 1) {
dp[i] = dp[i-(j*j)] + 1;
}
}
}
System.out.println(dp[n]);
}
private void solution() {
}
}
'Algorithm > baekjoon' 카테고리의 다른 글
동물원 (0) | 2022.02.15 |
---|---|
RGB거리 (0) | 2022.02.15 |
연속합 (0) | 2022.02.15 |
가장 긴 증가하는 부분 수열 4 (0) | 2022.02.15 |
가장 긴 증가하는 부분 수열 (0) | 2022.02.15 |