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

+ Recent posts