[백준] DP - 1699번 제곱수의 합(다른 풀이 봄)
* 공부 목표
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
문) 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.
풀이
1. 테이블 정의 : dp[i] = i를 구성하는 최소 항의 개수
2. 점화식
- 제곱수인 경우, dp[i] = 1;
- 그 외, dp[i] = Math.min(dp[i], dp[j] + dp[i-j]);
3. 초기값 : dp[0] = 0; dp[1] = 1;
<점화식 도출>
dp[1]~dp[10] 까지 해당하는 값을 쭉 나열해 보았다.
**dp[]는 편의상 생략함.
1 = 1²
2 = 1² + 1²
3 = 1² + 1² + 1²
4 = 2²
5 = 2² + 1²
6 = 2² + 1 + 1
7 = 2² + 1 + 1 + 1
8 = 2² + 2²
9 = 3²
10 = 3² + 1
다시 정리해보면, 이렇게 작성할 수 있다.
dp[10] = dp[1]+dp[9] = 2 ✅
= dp[2]+dp[8] = 4 ...
제일 처음 값을 말도 안 되는 큰 값을 배정해두고,
현재 i값이 제곱수일 때와 아닌 경우의 수를 나누어 식을 작성하면 된다.
스스로 생각했을 때 어디까지 했나? (망한 풀이입니다.)
중첩 for문을 활용하여, n - (i*i) 반복하는 과정을 구상.
먼저 제곱수의 조건을 생각했다.
1) n > (i * i) 를 만족시킨 값.
2) 1의 조건식을 만족시키는 수 중 n에 가까운 수부터 for문을 돌림.
그러다보니 제곱수의 조건이 한도 끝도 없고 말도 안 되는 조건식을 달아야 했음.
dp는 값을 누적하여 효율적이게 계산하는 것이 특징인데, 전혀 효율적이지도 않았음.
결국, 풀이를 봤을 때 그나마 쓸만한 구상은 n값에서 뺀다 정도...?
코드
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i=2; i<=n; i++) {
dp[i] = 99999;
for(int j=1; j<=i/2; j++) {
//자기가 제곱수인 경우
if(j*j == i) {
dp[i] = 1; break;
} else {
dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
}
}
}
br.close();
bw.write(String.valueOf(dp[n]));
bw.flush();
bw.close();
}
}솔직히 여러모로 자괴감이 많이 들었다.
dp문제를 계속 풀었다하나, 처음 보는 유형이면 다시 원점으로 돌아가는 것 같다.
분하기도 하고, 스스로의 멍청함에 개탄하기도 한다.
그래도 어떡하나...
알고리즘은 많이 풀어보고 꾸준히 생각한 사람에게 유리하다는 마음으로 지속해 나가자고 다짐한다.
[참고] https://jainn.tistory.com/274