[백준] 17626 Four Squares - 동적계획법(DP, Dynamic Programming) JAVA

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

17626번: Four Squares

코드설명

처음에 문제를 읽고서 그리디하게 완전탐색을 진행하며 가장 큰 숫자 순으로 하면 최적의 숫자가 나올 것이라고 생각했었습니다.

그러나, DP를 활용하여 최적의 수를 찾아가면서 진행해야합니다.

예를들면, 12가 있을경우 3^2 + 1 + 1 + 1 = 4 개의 숫자가 쓰였습니다. 그러나, 2^2 + 2^2 + 2^2 = 12 로 3개의 숫자가 쓰였습니다. 

 

n = 0 이면 0 입니다.

n = 1 일떄 , 1^1 , 총 1 개 쓰였습니다.

n = 2 일떄,  1^1 + 1^1 ,총 2 개 쓰였습니다.

n = 3 일떄, 1^1 + 1^1 + 1^1, 총 3 개 쓰였습니다. 이떄, dp[2] + 1 입니다. dp[2] 인 이유는 dp[ 3 - 1^1 ] 입니다.

n = 4 일때, 2^2 , 총 1개 쓰였습니다. 이떄, dp[0] + 1 입니다. dp[0] 인 이유는 dp[ 4 - 2^2 ] + 1 입니다.

n = 5 일때, 2^2 + 1^1 , 총 2 개 쓰였습니다. 이때, dp[1] + 1 입니다. dp[1] 인 이유는 dp[ 5 - 2^2 ] + 1 입니다.

...

계속해서 같은 로직으로 진행됩니다.

이와 같은 규칙을 찾아서 진행해야합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {	
	public static int N, M;
	public static int temp = 0, sum = 0;
	public static int[] dp;
	public static int resultcnt = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken()); // 민혁이가 영수에게 질문한 횟수
    	
    	dp = new int[N+1];
    	dp[0] = 0;  // 0은 0개
    	dp[1] = 1;  // 1은 1^1
    	
    	for(int i=2; i<=N;i++) { 
    		int temp = Integer.MAX_VALUE;
    		for(int j=1; j*j <= i;j++) {
    			temp = Math.min(temp, dp[i-j*j] + 1);  //DP 계산식 dp[i] = Math.min(dp[i], dp[i-j*j] + 1 );
    		}
    		dp[i] = temp;
    	}
    	
    	System.out.println(dp[N]);

	}
}

 

 

 

처음에 그리디하게 접근하여 풀었던 문제입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {	
	public static int N, M;
	public static int temp = 0, sum = 0;
	
	public static int resultcnt = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken()); // 민혁이가 영수에게 질문한 횟수
    	
    	boolean endFlag = false;
    	for(int i=0;i<4;i++) {
    		
    		temp = 0;
    		resultcnt += 1;
    		for(int j=1; ;j++) {
    			int square = j * j;
    			
    			if( sum + square == N) {
    				sum += square;
    				endFlag = true;
    				break;
    			}else if( sum + square > N){
    				sum += (j-1) * (j-1);
    				System.out.println(sum);
    				break;
    			}
    		}
    		if(endFlag == true) {
    			break;
    		}
    		
    	}
    	System.out.println(resultcnt);
    	
    
	}
}

 

 

 

정답코드 2입니다.

최적 부분구조를 만족하도록 코드를 작성했습니다.

메모이제이션을 활용하여 중복계산을 삭제합니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, M, Q;
    private static int[] arr;
    private static int[] cache;
    private static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		cache = new int[N + 1];
		Arrays.fill(cache, -1);
//		System.out.println(Math.sqrt(N));
		System.out.println(func(N));
    }
    
    //func(int n) : 자연수 n을 만들 수 있는 최소 개수의 제곱수를 반환한다.
    public static int func(int n) {
    	if(n == 0) {
    		return 0;
    	}
    	if(cache[n] != -1) return cache[n];
    	int ret = 50001;
    	int start = (int) Math.sqrt(n);
    	for(int i = start; i >= 1; i--) {
    		int square = (int) Math.pow(i, 2);
    		ret = Math.min(ret, func(n - square) + 1);
    	}
    	return cache[n] = ret;
    }
}