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

 

문제

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

 

 

 

 

 

 

 

 

 

 

 

 

풀이

처음에는 큰 제곱을 빼주고 개수를 구하는 식으로 짰다.

(이렇게 하면 될 줄 ,,, ) 

 

예를 들어 41 = 16 + 25로 2 가 나올 수도 있고, 36 + 4 + 1로 3 이 나올 수도 있다.

 

하지만 내가 짠 건 큰 제곱을 빼주고 개수를 세는 식으로 짰기 때문에 36 + 4 + 1로 3이 반환되어 틀린 로직이 되었다. 

 

그래서 배열을 하나 선언해서 여러 경우 중 가장 작은 값을 넣어서 다시 문제를 풀었다. 

 

 

입력값 10의 최솟값은 2이다.

arr[1] = 1

arr[2] = 2

arr[3] = 3

arr[4] = 2^2 = 1 

arr[5] = arr[4] + arr[1] = 1 + 1 = 2

arr[6] = arr[4] + arr[2] = 1 + 2 = 3

arr[7] = arr[4] + arr[3] = 1 + 3 = 4

arr[8] = arr[4] + arr[4] =  1 + 1 = 2 

arr[9] = 3^2 = 1 

arr[10] = arr[9] + arr[1] = 1 + 1 = 2  

              arr[6] + arr[4] = 3 + 1 = 4

 

위처럼 arr[10] 처럼 여러개의 값이 구해질 경우 Math.min()을 통해 최솟값을 구하는 로직을 만들어줬다.

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static int[] arr = new int[100001];

    /**
     * 최소 개수 구하기
     * 
     * @param x
     */
    public static void square(int x) {
        int num = (int) Math.sqrt(x);
        int min = 10001;
        // 제곱근이라면 1개 
        if (num * num == x) {
            arr[x] = 1;
        } else if (num >= 2) {
            for (int i = 2; i <= num; i++) {
                int number = x - i * i;
                if (arr[number] == 0) {
                    square(number);
                }
                if (arr[x - number] == 0) {
                    square(x - number);
                }
                min = Math.min((arr[number] + arr[x - number]), min);
            }
            arr[x] = min;
        }

    }

    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 num = Integer.parseInt(br.readLine());

		// 1, 2, 3은 한 가지 경우의 수밖에 없으므로 초기값 설정 
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;

        square(num);

        bw.write(String.valueOf(arr[num]));
        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

 

 

 

 

정답