[백준] code.plus(다이나믹 프로그램 part 1,JAVA)1699번, 제곱수의 합

문제 링크

1699번: 제곱수의 합

---

주의사항

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

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

---

문제 설명

---

접근 방법

다이나믹 프로그램

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 입력값을 제곱수의 합으로 나타내야 합니다.

2. 제곱수를 나타내는 여러 경우의 수 중 최소 제곱수를 사용하는 제곱수 개수를 결과로 출력합니다.

 

배열

 

DP : 메모이제이션 배열

 

DP 배열을 이용하여 가장 길이가 긴 증가하는 수열을 구하였습니다.

 

DP[i]는 i의 값에 대하여 제곱수로 나타내는 최소 개수를 가지게 됩니다.

 

DP의 값을 예제입력 1에 입력값에 대한 표로 나타낸다면

	1	2	3	4	5	6	7
DP	1	2	3	1	2	3	4

 

위에 표를 구한 뒤 저는 입력값 이하의 가장 큰 제곱수를 통해 구하면 최소 개수를 구할 수 있다고 생각하여 코드를 작성하였지만 틀렸습니다.

반례로 입력값을 41일 때 살펴보면

41이하의 가장 큰 제곱수는 36을 이용하면

6² + 2² + 1² = 41

 

하지만 최소 개수는 5² + 4² = 41로 2개입니다.이런 반례를 통해서 입력값보다 작은 제곱수를 모두 확인하여 최소 개수인 값을 찾아야 합니다.

 

예제입력 1을 구할 때를 살펴보면

 

입력값 = 7

7보다 작은 제곱수 : 1, 4

 

제곱수 1을 사용할 때 : 4개

1² + 2² + 1² + 1² = 7

 

제곱수 4을 사용할 때 : 4개

2² + 1² +1² + 1² = 7

 

위 입력은 동일하여 결과는 4

 

아까 반례로 입력값 41을 살펴보면

41보다 작은 제곱수 : 1, 4, 9, 16, 25, 36

 

제곱수 1을 사용할 때 : 3개

1² + 6² + 2² = 41

 

제곱수 4을 사용할 때 : 3개

2² + 6² + 1² = 41

 

제곱수 9을 사용할 때 : 6개

3² + 5² + 2² + 1² + 1² + 1² = 41

 

제곱수 16을 사용할 때 : 2개

4² + 5² = 41

 

제곱수 25을 사용할 때 : 2개

5² + 4² = 7

 

제곱수 36을 사용할 때 : 3개

6² + 2² + 1² = 41

 

해당 결과는 2

 

해당 제곱수의 규칙을 작성하면

DP[i] > DP[i - 입력값보다 작은 제곱수] + 1일 때

DP[i] = DP[i - 입력값보다 작은 제곱수] + 1

 

위 경우를 반복하여 DP를 구성한 뒤 DP[N]을 결과로 출력합니다.

 

문제에 해결알고리즘은

1. 입력값을 받아서 규칙을 적용해서 DP[]를 구성합니다.

2. DP[n]을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• DP  구성하는 sum함수를 만들었습니다.
• BufferedWriter에 DP[n]의 값을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• sum은 반복문을 통해 위에 설명한 규칙을 적용시켜주었습니다.

 

 

결과 코드

import java.io.*;
public class Main{
	public static int[] DP;		//메모이제이션 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
    	int N = Integer.parseInt(br.readLine());		//입력값 저장
    	DP = new int[N+1];
    	int result = sum(N);		//함수 실행 및 함수 결과 저장
    	bw.write(result + "\n");		//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //-------DP[]구성하는 함수------
    public static int sum(int n) {
    	for(int i=1;i<=n;i++) {		//1~n까지 반복
    		for(int j=1;j*j<=i;j++) {		//i의 값에 제곱수만큼 반복
    			if(DP[i] > DP[i-j*j] + 1 || DP[i] == 0 )	//제곱수 개수 작은 값 찾았을 때
    				DP[i] = DP[i-j*j] + 1;
    		}
    	}
    	return DP[n];		//결과 반환
    }
}