📙[Algo] 24.03.10 알고리즘

알고리즘 문제) BOJ 1699. 제곱수의 합

• 링크 : https://www.acmicpc.net/problem/1699

문제 요약

• N을 제곱수들의 합으로 표현할 때 그 항의 최소 개수 구하기

시간 제한

• 2초

입력

• 자연수 N
  • 1≤N≤10만

출력

• 자연수N을 제곱수의 합으로 나타낼 때 항의 최소 개수

접근법

1. 완전 탐색으로 생각하기
   
   ⇒ 22 + 11 + 11 + 11
   • sqrt(N)보다 작거나 같은 수들 중 가장 큰 정수 k부터 시작
   • N - k*k도 마찬가지로 진행!
2. 백트랙킹으로 생각하기
   • remain : 남은 값
   • cnt : 항 개수

static void recur(int remain, int cnt) {

      if (remain == 0) {
          answer = Math.min(answer, cnt);
          return;
      }

      for (int i = (int)Math.sqrt(remain); i >= 1; i--) {
          remain -= i*i;
          recur(remain, cnt + 1);

          remain += i * i;
      }

  }

코드

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

public class Main {
    static int N;
    static int[] dp;
/*
     1. 백트랙킹으로 구현하기
    static void recur(int remain, int cnt) {

        if (remain == 0) {
            answer = Math.min(answer, cnt);
            return;
        }

        for (int i = (int)Math.sqrt(remain); i >= 1; i--) {
            remain -= i*i;
            recur(remain, cnt + 1);

            remain += i * i;
        }

    }
 */

    // 2. 함수  + 메모이제이션 적용하기 => 현재 남은 숫자에서 제곱수의 합으로 나타낼 수 있는 가장 최소 항을 반환
    static int recur( int remain) {

//        if (remain < 0) return 1 << 30;

        if (remain == 0) return 0;

        if (dp[remain] != 1<<30) return dp[remain];

        for (int i = (int)Math.sqrt(remain); i >= 1; i--) {

            dp[remain] = Math.min(recur( remain - i * i) + 1, dp[remain]);

        }

        return dp[remain];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        dp = new int[N + 50];
        Arrays.fill(dp, 1<<30);

        bw.write(String.valueOf(recur(N)));
        bw.flush();
        bw.close();
        br.close();
    }
}