[DP] 백준 - Four Squares

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

17626번: Four Squares

 

 

-문제해설

처음에 점화식을 잘못 세워서 약간 고생을 했다;

 

주어진 수를 제곱합으로 만들기 위해 필요한 최소의 제곱합의 개수를 구하는 문제이다.

 

제곱합의 개수가 담기는 배열을 dp라고 하자.

dp[1] = 1이다. 왜냐하면 1을 만들 수 있는 제곱합의 수는 1의 제곱밖에 없기 때문에 개수는 1개이다.

 

2를 만들기 위한 최소의 제곱합의 개수는

i - j*j = 2 - 1*1 = 1

dp[2] = dp[1] + 1 = 2

 

3은

i - j*j = 3 - 1*1 = 2

dp[3] = dp[2] + 1 = 2 + 1 = 3

 

4를 만들기 위한 최소의 제곱합의 개수는

i - j*j = 4 - 1 = 3

i - j*j = 4 - 4 = 0

 

dp[4] = dp[3] + 1 = 3 + 1 = 4

또는

dp[4] = dp[0] + 1 = 1

이므로 답은 1이다.

 

8을 만들기 위한 최소의 제곱합의 개수는

i - j*j = 8 - 1 = 7

i - j*j = 8 - 2*2 = 8-4 = 4

 

dp[8] = dp[7] + 1 = 4

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

따라서 정답은 2이다.

 

 

12를 만들기 위한 최소의 제곱합의 개수는

i - j*j = 12 - 1 = 11

i - j*j = 12 - 4 = 8

 

dp[12] = dp[11] + 1 = 4

dp[12] = dp[8] + 1 = 3

따라서 정답은 3이다.

 

 

즉 j는 1부터 j*j가 i이하까지 반복하면서 가장 제곱수가 적은 것을 출력하면 된다.

 

 

 

-자바

package dp;

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

public class BJ17626 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		int[] dp = new int[n+1];
		dp[1] = 1;
		
		int min = Integer.MAX_VALUE;
		for( int i=2; i<=n; i++ ) {
			min = Integer.MAX_VALUE;
			
			for( int j=1; j*j<=i; j++ ) {
				int tmp = i - j*j;
				min = Math.min( min, dp[tmp] );
			}
			dp[i] = min + 1;
		}
		
		System.out.println( dp[n] );
	}
}

 

-파이썬( pypy3로 해야지 통과 )

n = int( __import__('sys').stdin.readline() )
dp = [0] * (n+1)
dp[1] = 1
for i in range( 2, n+1 ):
    m = 9999
    for j in range( 1, i+1 ):
        if j*j > i: break
        tmp = i - j*j
        m = min( m, dp[tmp] )
    dp[i] = m + 1
print( dp[n] )