Dazzling 개발 노트
[백준] 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
