[백준] 17626 - Four Squares JAVA

Solved.ac Class 완전정복 프로젝트

Class : 3 ~ 3 ++

 

---

링크

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

17626번: Four Squares

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력
입력은 표준 입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력
출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

접근방법

 n을 만들 수 있는 제곱수들의 최소 개수를 요구하는 문제이다.  f(N)을 N을 만들 수 있는 최소 제곱수들의 개수라 정의할 때, f(11339)는 4라 할 수 있다. 해당 문제를 그리디 알고리즘으로 생각한다면, 아마 이 예제가 제일 큰 반례일 것이다.  그리디 알고리즘으로 생각했을 때는, f(11339)는 5가 나오기 때문이다. 그렇다면 어떻게 해결해야 할까? 정도의 물음을 가지고 풀이로 접근한다.

풀이

 

 문제를 보면서, 확인해야할 포인트는 이전에 구한 최소 값을 사용할 수 있는가 이다. f(27)이란 값이 있다고 하면, 이문제는 f(25)+f(2)의 문제로 나눌 수 있다. 즉, 분할 정복이 가능한 DP 문제라는 것이다. 

 

DP문제임을 알았다면, 최소를 구할 비교 조건을 잘 정하기만 하면된다. 특정 N이 존재할 때,  N보다 작은 모든 제곱수들을 확인하며, 최소 값을 찾아나가면 된다.

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test =new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);

        int num =sc.nextInt();


        System.out.println(solution(num));
    }

    private int solution(int num) {
        int[] arr = new int[50001];
        arr[0]=0;

        //i를 만들 수 있는 제곱의 최소갯수 ?

        for (int i = 1 ; i <= num;i++){
            arr[i] = i;
            for (int j = 0; j*j <= i ;j++){
                //모든 경우의 수 계산다 해봄
                arr[i] = Math.min(arr[i],1+arr[i-j*j]);
            }
        }


        return arr[num];
    }
}

결과

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.