[백준] 1699: 제곱수의 합

문제

문제 풀이

제곱수들은 주어진 자연수 N보다 작아야 하는 조건과 더불어, 현재 dp값보다 작아야 한다.

N까지의 dp값을 N을 제곱근으로 가장 길게 표현할 수 있는 11 N, 즉 N으로 초기화하였다.

이중 반복문을 사용하여서 i가 N까지 dp를 채우는 동안 j의 제곱근이 i를 초기화지 않은 조건 하에 dp[i- j*j] + 1(j를 선택한 counting) 이 현재 dp[i]값 보다 작을 경우 dp[i]로 선택한다.

코드

package DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ANS1699 {

    static int N;
    static int[] dp;

    public static void main(String[] args) throws IOException {


        //선언
        BufferedReader  bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        //dp선언 및 초기화
        dp = new int[N+1];
        dp[0] = 0;

        for(int i = 1 ; i <= N; i++){
            dp[i] = i;
            for(int j = 1; j*j <= i ; j++){
                if(dp[i- j*j]+1 < dp[i]){
                    dp[i] = dp[i-j*j] +1;
                }
            }
        }
        System.out.println(dp[N]);
    }
}

---

11053 가장 긴 증가하는 수열, 11722 가장 긴 감소하는 수열 문제와 비슷한 방식으로 문제를 풀 수 있었다.

처음엔 시간초과가 나왔는데 아마도, j의 제곱을 Math.pow(j,2)로 표현했기 때문인것 같다. 이를 j*j로 수정하니 시간초과 결과가 나오지 않았다.

또한, 처음 코드 작성시 j를 i까지 검토하고, i값에서 j값을 뺀 수가 양수 일때 고려하는 방향으로 짰었는데, 이는 ArrayindexOutofBounds가 나왔다.

아직 동적계획법을 알기에 멀지만,, 그래도 조금씩 내가 작성한 코드가 맞는 걸 보면 뿌듯하구만!!