[백준] 17626 - Four Squares (Java)

[백준] 17626 - Four Squares (Java)

문제

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

풀이/후기

다들 패턴을 찾느라 오래걸렸다고 하는데

난 스스로 찾기는 커녕 이해하는데도 오래 걸렸다,,ㅋㅋ

 

dp[1] = 1
dp[2] = dp[1] + 1 = 2
dp[3] = dp[2] + 1 = 3
dp[4] = 1
dp[5] = dp[2^2] + dp[1] = 2
dp[6] = dp[2^2] + dp[2]  = 3
dp[7] = dp[2^2] + dp[3] = 4 
dp[8] = dp[2^2] + dp[2^2] = 2

 

숫자 i는 자신의 제곱수(dp[j*j])들을 기준으로 제곱수를 뺀 나머지 값의 합을 구하면 된다. 
→ 따라서 점화식은 dp[i] = dp[i- j*j] + dp[j*j] 이라고 볼 수 있다.  (제곱 수 dp[j*j] , 나머지 합 dp[i-j*j])

이제 계산을 하면 되는데 dp[j*j] =1로 고정값이므로 가변값 dp[i-j*j]만 비교해주면 된다.

코드

package DynamicProgramming;

import java.io.*;

public class Problem17626 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int[] arr = new int[N + 1];

		arr[1] = 1;
		for (int i = 1; i < N + 1; i++) {
			int min = Integer.MAX_VALUE;

			for (int j = 1; j * j <= i; j++) {
				int temp = i - (j * j);
				min = Math.min(min, arr[temp]);
			}

			arr[i] = min + 1;
		}

		System.out.println(arr[N]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/a3fb9f0e31f9e0efa2cf19c3791609389ad58a76

참고

패턴 상세 설명

https://loosie.tistory.com/229

https://steady-coding.tistory.com/18