[BOJ/Java] 17626. Four Squares

[BOJ/Java] 17626. Four Squares

17626번: Four Squares

---

문제 해석

이 문제는 주어진 수 𝑁N을 최소 개수의 제곱수 합으로 표현할 때 필요한 제곱수의 개수를 찾는 문제이다. 예를 들어, 𝑁=13이면 2^2+3^2=13이므로, 최소 개수는 2개이다.

풀이 과정

• 다이나믹 프로그래밍(DP) 사용: 문제를 해결하기 위해 다이나믹 프로그래밍 기법을 적용한다.
• DP 배열 초기화: dp[i]는 숫자 𝑖i를 제곱수의 합으로 나타낼 때 필요한 최소 제곱수의 개수이다.
• 점화식 계산: 각 숫자 𝑖i에 대하여 가능한 모든 제곱수 𝑗^2를 사용하여, 𝑑𝑝[𝑖−𝑗^2]를 참조하며 𝑑𝑝[𝑖]의 값을 갱신한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No17626;

import java.io.*;

public class Main {
	private static int N;  // 주어진 수 N

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());  // 입력 받은 N
		
		int[] dp = new int[N + 1];  // DP 배열
		dp[1] = 1;  // 초기값 설정
		
		int min;
		for (int i = 1; i <= N; i++) {
			min = Integer.MAX_VALUE;
			
			for (int j = 1; j * j <= i; j++) {  // 모든 j에 대하여 j^2이 i 이하일 때
				int k = i - j * j;
				min = Math.min(min, dp[k]);  // 최소값 갱신
			}
			
			dp[i] = min + 1;  // 최소 제곱수의 개수 갱신
		}
		
		sb.append(dp[N]);  // 결과 출력
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}
}

시간 복잡도 분석

각 숫자 𝑖에 대하여, 가능한 𝑗의 개수는 최대 𝑖i​개이므로, 이 알고리즘의 시간 복잡도는 𝑂(𝑁root(𝑁))이다.

느낀점

Four Squares 문제는 수학적으로 중요한 문제 유형 중 하나로, 다이나믹 프로그래밍을 이용해 최적화 문제를 해결하는 기본적인 접근법을 보여준다. 이 문제를 통해 제곱수의 합으로 수를 표현하는 문제를 효율적으로 해결하는 방법을 배울 수 있었다. 이러한 문제는 컴퓨터 과학뿐만 아니라 순수 수학에서도 연구되는 중요한 주제이다.