알고리즘 - 백준 - 1699 - 제곱수의 합 - JAVA

김성일·2024년 10월 19일

DP 백준 실버 알고리즘

알고리즘

목록 보기

18/23

문제 바로가기

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

문제 소개 및 재정의

https://velog.io/@bed_is_good/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-2294-%EB%8F%99%EC%A0%842-JAVA

저번에 풀이한 동전2랑 같은 문제다.
N이하의 제곱수들을 동전으로 사용하고, 가격 K가 N이 된다.
따라서 코드를 제외한 나머지 것들은 동전2를 참고하면 되므로 비워두겠다.

문제 패턴

어떻게 풀까? -

포인트

코드

package study.week14;

import java.io.*;
import java.util.*;
public class BOJ_1699_제곱수의합2 {
	// 입력고정
	static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
	// 세팅
	static int N;
	static ArrayList<Integer> sub = new ArrayList<>(); // N의 최대값이 10^5이므로 그보다 더 큰 제곱수를 사용할일은 없음.
	static int [][] dp;
	static int [] minis;
	static int INF = Integer.MAX_VALUE;
	// 메소드
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		N = Integer.parseInt(input.readLine());
		// 세팅
		//// N이하인 제곱수 구해서 ArrayList에 넣기
		for (int n = 0+1; n < N+1; n++) {
			int nSquare = (int) Math.pow(n, 2);
			if(nSquare <= N) {
				sub.add(nSquare);
			} else {
				break;
			}
		}
		//// dp 테이블 초기화
		dp = new int[N+1][sub.size()];
		
		minis = new int[N+1];
		// 작업
		//// dp 테이블 채우기. dp[n][k] = 제곱수 k를 더했을때 n이 된다. 이때 더한 제곱수의 최소 개수.  = minis[n-k]+1 = n-k를 만드는데 더한 제곱수의 최소개수 +1. (n-k가 음수면 못 만드니까 INF.)
		for (int row = 0+1; row < N+1; row++) { // row는 0+1부터 시작해야 됨. 0번 행은 전부 0으로 초기화해야됨. 좀 더 의미있게 하려면 여기도 INF로 채우고. sub.get(col)의 값이 row와 일치할때 1을 초기화하는게 의미적으로 맞음.
			int mini = INF;
			for (int col = 0; col < sub.size(); col++) {
				int prev = row - sub.get(col);
				if(prev<0) {
					dp[row][col] = INF;
				} else {
					if(minis[prev]==INF) {
						dp[row][col] = INF;
					} else {
						dp[row][col] = minis[prev]+1;
						mini = Math.min(mini, dp[row][col]); // 행의 최소값 업데이트
					}
				}
			} // dp테이블 행 채우기 끝. minis의 동일행 채우기 시작해야함.
			minis[row] = mini;
		}
		// 출력
		System.out.println(minis[N]);
		
		
	}// 메인 종료

}

번외 : 그리디한 풀이 (실패함)

package study.week14;

import java.io.*;
public class BOJ_1699_제곱수의합3 {
	// 입력고정
	static BufferedReader input = new  BufferedReader(new InputStreamReader(System.in));
	// 세팅
	// 메소드
	static void removeBigPart(int prevNum, int depth) {
		// 바닥 조건
		if(prevNum==0) { // 직전에 N을 완성했다는 의미.
			System.out.println(depth);
			return;
		}
		// 재귀 조건
		int temp = (int) Math.sqrt(prevNum); 				// 제곱근에서 정수부만 취함. 내림은 int로 형변환해주면서 자동으로 된다.
		int nextNum = prevNum - ((int)Math.pow(temp, 2)); 	// 전체 수에서 가장 큰 제곱수를 빼준다. 남은 수 또한 다른 제곱수의 합으로 표현이 가능하다. 
															//남은 수는 제곱근의 소수부의 제곱값에 해당된다.
		removeBigPart(nextNum, depth+1); 					// depth는 더해준 제곱수의 개수를 의미한다. 제곱수를 하나 더해줬으므로 추가한다.
	}
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		int N = Integer.parseInt(input.readLine());
		// 세팅
		// 작업
		removeBigPart(N, 0);
		// 출력
		
	}// 메인 종료

}