Baekjoon/[3] DP

[백준] 1699번 제곱수의 합 JAVA (자바) 풀이

Poorm 푸름 2024. 7. 1. 17:03

문제 1699번 (DP)

 : 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다

   예를 들어 11 = 3² + 1² + 1² (3개 항) 또는 11 = 2² + 2² + 1² + 1² + 1² (5개 항) 가능하다

   11 제곱수 항의 최소 개수는 3이다

   주어진 자연수 N 제곱수 항의 최소개수를 구하는 프로그램

 

 

[입력]


 :  첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

 

 

[출력]

 

 :   제곱수 항의 최소 개수를 출력

 


[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)  보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결 작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization) 타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때 모두 계산해야 답이 나올 때
재귀 반복문
시간 복잡도 O(n) 시간 복잡도 O(n)

 

1. dp 규칙 찾기

  • dp[i] = i
    1. 어느게 제곱수가 될 지 모르니 1~N까지 돌면서 하나를 고정한다

  • for(int j=1; j*j<=i; j++)
    1. 고정된 수가 제곱으로 표현 가능한 지 확인
      예로 i = 12 / 1~3까지는 제곱해도 12 안에서 표현 가능하지만
      4는 제곱하면 16이 되므로 제곱수로 표현 불가

  • dp[i]>dp[i-j*j]+1
    • dp[i] = i로 두는게 좋을지
      dp[i-j*j] = i란 숫자 안에서 제곱이 되는 애는 제곱으로 만드는게 좋을지 
    • 뒤에 +1을 붙이는 건 제곱의 항을 count 한다는 의미다 

  • dp[i] = dp[i-j*j]+1;
    • 제곱으로 만드는게 더 작다고 판단했다면 실제로 dp를 if 조건문처럼 갱신해준다

 

 

 [코드]

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));
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        
        for(int i=1; i<=N; i++){
            dp[i] = i;
            for(int j=1; j*j<=i; j++){
                if(dp[i]>dp[i-j*j]+1){
                    dp[i] = dp[i-j*j]+1;
                }
            }
        }
        System.out.println(dp[N]);
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int dp[] = new int[1000001];  dp 배열 초기화        
        
 :  for(int i=1; i<=N; i++){
            dp[i] = i;  제곱으로 만들 하나의 수 고정
            for(int j=1; j*j<=i; j++){  i를 넘어서지 않는 제곱근 j를 탐색
                if(dp[i]>dp[i-j*j]+1){  그냥 두는 것보다 제곱으로 만드는게 더 작은 값이라면
                    dp[i] = dp[i-j*j]+1;  그렇게 갱신해주기
                }
            }
    }


 :  System.out.println(N);  결과 출력
 
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

저작자표시