https://www.acmicpc.net/problem/1699
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net
코드설명
DP 문제입니다.
문제로직은 다음과 같습니다.
dp[1] = 1개 -->1^2
dp[2] = 2개 --> 1^2 + 1^2
dp[3] = 3개 --> 1^2 + 1^2 + 1^2
dp[4] = 1개 --> 2^2
dp[5] = 2개 --> 2^2 + 1^2
dp[6] = 3개 --> 2^2 + 1^2 + 1^2
dp[7] = 4개 --> 2^2 + 1^2 + 1^2 + 1^2
dp[8] = 2개 --> 2^2 + 2^2
dp[9] = 1개 --> 3^2
dp[10] = 2개 --> 3^2 + 1^2
생각해보면, dp[10], 즉 10이라는 숫자를 만들려면, 1+9, 2+8, 3+7, 4+6, 5+5 를 만드는 경우의 수에서 최소경우를 구하면 됩니다.
이 과정에서 만약 dp[4]와 같이 만드는 숫자의 경우 1+3, 2+2 보다 2^2 가 더 빠른 숫자이므로 이런 경우에는 1가지로 표현됩니다.
위의 과정을 나타내면 됩니다.
다른방법으로는, 이번에도 역시 dp[10]을 만드는 과정입니다.
이떄 dp[10]을 만드는 방법은
9에서 1^2 을 더하는 방법.
6에서 2^2 를 더하는 방법
1에서 3^3을 더하는 방법이 있습니다.
이때 dp[0] = 0 으로 처리하여 만약에 9와 같은 제곱수라면 dp[9] = dp[0] + 1 처리되어 최소값을 구합니다.
이렇게 제곱수를 빼면서 최소값을 갱신하여 제곱수로 만들 수 있는 최소의 경우를 만들 수 있습니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { public static int N; public static int[] dp; public static int[] arr; public static int answer; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); dp = new int[100001]; N = Integer.parseInt(st.nextToken()); dp[1] = 1; for(int i=2;i<=N;i++) { int minValue = 100001; for(int j=1; j<=(int)i/2;j++) { if(j*j == i) { // j*j == i 라면 ( 즉, 3 * 3 == 9 라면 최소값은 무조건 해당값은 1개입니다. minValue = 1; break; } minValue = Math.min(minValue, dp[j] + dp[i-j]); } dp[i] = minValue; } System.out.println(dp[N]); } }
두번쨰 풀이
dp[i] = dp[i - j*j] + 1 을 이용
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; public class Main { public static int N; public static int[] dp; public static int[] arr; public static int answer; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); dp = new int[100001]; N = Integer.parseInt(st.nextToken()); 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]); } }
메모이제이션을 활용한 코드입니다.
package Main; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int C, N, M; public static int answer = 0; public static int[] cache = new int[100001]; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); Arrays.fill(cache, -1); N = Integer.parseInt(st.nextToken()); System.out.println(func(N)); } private static int func(int n) { if(n == 0) return 0; if(cache[n] != -1) return cache[n]; int ret = 100001; int sqrt = (int) Math.sqrt(n); for(int i=1; i<=sqrt; i++) { ret = Math.min(ret, func(n - i * i) + 1); } return cache[n] = ret; } }
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1309 동물원 - 동적계획법(Dynamic Programming, DP) JAVA (0) | 2023.09.14 |
---|---|
[백준] 15988 1, 2, 3 더하기 3 - 동적계획법(Dynamic Programming, DP) JAVA (0) | 2023.09.14 |
[백준] 14002 가장 긴 증가하는 부분 수열 4 - DP + Stack + LIS JAVA (0) | 2023.09.13 |
[백준] 2193 이친수 - DP JAVA (0) | 2023.09.13 |
[백준] 15990 1, 2, 3 더하기 5 - 동적계획법(Dynamic Programming, DP) JAVA (0) | 2023.09.13 |