[백준] 17626 - Four Squares (JAVA)

정보

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 3
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/17626
8. 푼 날짜 : 2023.03.06

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 풀이과정

점화식을 유도해내지 못해서 다른 사람의 코드를 참고했다. 1달 전에 풀었던 문제를 다시 풀었는데도 점화식을 유도해내지 못했다.
개인적으로 드는 생각인데 다른 사람들은 이걸 어떻게 점화식을 유도해냈는지 모르겠다.
풀이를 보고 '아~~' 하긴했지만 곧 바로 '음...?' 이라는 생각도 들었다.

1. dp 배열의 초깃값을 정한다. dp[0] = 0 , dp[1] = 1.
2. 다음의 점화식을 유도해내야 한다. dp[i]= min(dp[i - j * j ], dp[i] ) +1
3. 숫자 (n)을 입력받고 그 숫자에 해당하는 dp[n] 을 출력한다.

2번의 식을 풀어서 본다면
dp[10] 이라고하면
dp[10] 에 올 수 있는 dp 로는
dp[10-1 * 1]
dp[10-2 * 2]
dp[10-3 * 3] 이 올 수 있다.
이 중에서 가장 작은 값은 계속 누적되면서 이미 선행으로 정했었기 때문에
dp[10-3 * 3] 이 된다.
그리고 최종족으로 dp[10] 이 정해졌다면 그 값에 1을 더해준다.

3. 소스코드

import java.io.*;
import java.util.*;


public class Main{
	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb=new StringBuilder();

		
		int dp[]=new int[50001];
		dp[1]=1;
		for(int i=2;i<dp.length;i++) {
			dp[i]=Integer.MAX_VALUE;
			for(int j=1;j*j<=i;j++) {
				dp[i]=Math.min(dp[i-j*j],dp[i]);
			}
			dp[i]++;
		}
		
		int n=Integer.parseInt(br.readLine());
		System.out.println(dp[n]);
		
	}
}

4. 결과

이전에 이 문제를 푼 것은 1달전..
만약 다음에 또 이문제를 풀었는데 또 모르면 안되도록 상기해야 할 것이다.

5. 회고

점화식 유도를 그래도 최소한 30분씩은 해보고 풀이를 보고 있다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212