[백준] 1669 - 제곱수의 합(JAVA)

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

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

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

2. 풀이과정

사실 이 문제를 봤는데
https://www.acmicpc.net/problem/17626
이 문제와 완전히 똑같다는 것을 알았다.
한 가지 다른 것은 n의 범위인데, 여기서는 n이 2배 커졌다.
그래서 초기 배열을 50,000의 범위에서 100,000 까지만 늘려주니 바로 통과했다.

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[100001];
		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. 결과

5. 회고

전의 문제와 똑같아서 별 달리 어려울 게 없다고 느껴졌다.

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