[백준] 알고리즘 분류(브루트포스 알고리즘,JAVA)17626번, Four Squares

문제 링크

17626번: Four Squares

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1.  모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다.

2. n을 제곱수의 합으로 만들 수 있는 제곱수들의 최소 개수를 결과로 출력합니다. 

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 메모이제이션과 점화식을 이용하여 1~n까지 제곱수의 최소 개수를 구합니다.

 

3. DP[n]의 값을 결과로 출력합니다.

 

 

메모이제이션과 점화식

 

제곱수의 최소개수를 살펴보면

 

DP[1] = 1² = 1개

DP[2] = 1² + 1² = 2개

DP[3] = 1² + 1²  + 1² = 3개

DP[4] = 2² = 1개

DP[5] = 2² + 1² = 2개

DP[6] = 2² + 1² + 1² = 3개

.....

 

DP[i] = DP[i - 1²], DP[i - 2²] ... DP[i - √i²]의 값 중 가장 작은 값 + 1

※ +1을 하는 이유는 1²처럼 1개를 사용하기 때문입니다.

 

점화식

 

DP[i] = DP[i - j²]의 값 중 가장 작은 값 + 1 (1 ≤ j ≤ √i)

 

예를 들어

 

DP[5]를 구할 때DP[5 - 1²] , DP[5 - 2²] 중 작은 값

 

DP[4] = 1개, DP[1] = 1개

 

가장 작은 값 : DP[1] = 1개

 

DP[5] = 1 + 1 = 2

 

※ 2²를 사용하기 때문에 작은 값 +1을 진행합니다.

 

메모이제이션의 값들을 1~n값까지 점화식을 이용하여 채워주면

 

DP[n]의 값은 문제에 조건에 맞는 결과값이 됩니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

n = 25

 

2. 메모이제이션과 점화식을 이용하여 1~n까지 제곱수의 최소 개수를 구합니다.

점화식을 이용하여 메모이제이션 채우기!

DP[0] = 0

DP[1] = 1²  : DP[0] + 1 = 1개

DP[2] = 1²  : DP[1] + 1 = 2개

DP[3] = 1²  : DP[2] + 1 = 3개

DP[4] = 2²  : DP[0] + 1 = 1개

DP[5] = 2²  : DP[1] + 1 = 2개

DP[6] = 2²  : DP[2] + 1 = 3개

.....

DP[25] = 5²  : DP[0] + 1 = 1개

DP[26] = 1²  : DP[25] + 1 = 2개

 

3. DP[n]의 값을 결과로 출력합니다.

 

DP[n] = 2개

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 메모이제이션 DP[]를 구성하여 DP[1~n]까지 점화식을 이용하여 구합니다.
• DP[n]의 값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] DP = new int[n+1];
        DP[1] = 1;
        //DP[1~n] 구현
        for(int i=2;i<=n;i++){
            int min = Integer.MAX_VALUE;	//최소값 변수
            //DP[i]의 최소값 탐색
            for(int j=1;j * j <= i;j++){
                int index = i - j * j;
                min = Math.min(min, DP[index]);
            }
            DP[i] = ++min;	//최소값 + 1값 DP의 저장
        }
        bw.write(DP[n] + "");	//DP[n]의 값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}