[Java] 백준 1699 : 제곱수의 합

문제 링크

1.

1시간 소요.

노트에 대략적인 경우의 수를 모두 적어 점화식을 쉽게 구했으나, 오답이었다.

맞게 푼 것 같은데 잘못된 부분을 도저히 못 찾겠어서 다른 사람의 질문을 참고했다.

 

32의 결과값은 2가 나와야 하는데, 나는 5가 나왔다.

나는 $25+4+1+1+1$ 으로 계산했지만, $16+16$ 이라는 최소 개수가 존재한다.

이를 반영해서 코드를 수정했고 정답 메시지를 받았다.

 

비록 오류를 스스로 잡지는 못했지만 해설을 보지 않고 푼 것에 만족한다. 대신 코드가 조금 지저분한 것은 사실이다.

 

 

2.

$1 = 1$

$2 = 1+1$

$3 = 1+1+1$

$4 = 4$

$5 = 4+1$

$6 = 4+1+1$

$7 = 4+1+1+1$

$8 = 4+4$

 

규칙이 보이는가?

8을 예로 들면, 8과 가장 가까운 제곱수 4를 8에서 뺀 4의 dp 배열의 원소 값 + 1을 해주면 된다.

즉, 가장 가까운 제곱수를 뺸 값의 dp 원소 값 + 1이다.

 

이를 점화식으로 나타내면 다음과 같다.

 

dp[i] = dp[i - doubleSqrt[index - 1]] + 1;

 

 

하지만, 단순히 가장 가까운 제곱수를 기준으로 점화식을 세우면 최소 개수를 만족시키지 못한다. 위에서 말했던 32가 그 예시이다.

가장 가까운 제곱수부터 가장 작은 제곱수까지 계산을 해본 뒤 최소 개수를 선택해야 한다.

 

 

3.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        int[] doubleSqrt = new int[(int) Math.sqrt(n) + 2];

        if (n >= 1) {
            dp[1] = 1;
        }
        if (n >= 2) {
            dp[2] = 2;
        }
        if (n >= 3) {
            dp[3] = 3;
        }
        if (n >= 4) {
            for (int i = 1; i < doubleSqrt.length; i++) {
                doubleSqrt[i] = i * i;
            }

            int index = 2;
            for (int i = 4; i <= n; i++) {
                if (i == doubleSqrt[index]) {
                    dp[i] = 1;
                    index++;
                } else {
                    dp[i] = dp[i - doubleSqrt[index - 1]] + 1;
                    for (int j = index - 2; j > 0; j--) {
                        dp[i] = Math.min(dp[i], dp[i - doubleSqrt[j]] + 1);
                    }
                }
            }
        }

        System.out.println(dp[n]);

        /*
         * for (int i = 1; i <= n; i++) { System.out.printf("%d : %d\n", i, dp[i]); }
         */
        sc.close();
    }

}

 

 

4.

코드에 활용하지는 않았지만, 다음은 제곱수인지 확인하는 방법이다.

1. 제곱근 구하기

2. 그것을 정수로 변환하기

3. 제곱근 구한 것과 정수로 변환한 값이 같으면 그 수는 제곱수

 

    static boolean isValid(int n) {
        double doubleSqrt = Math.sqrt(n);
        int intSqrt = (int) doubleSqrt;

        return doubleSqrt == intSqrt ? true : false;
    }

 

 

[참고] http://bitly.kr/mEwpK402Ce1