[실버 3] [Java] 백준 17626번: Four Squares

아이디어

대체 이 문제 점화식을 어떻게 구하라는거야...하고 풀다가

dp를 쓰는데 greedy하게 풀었다. 그래서 처음에는 모두 넷 이하의 숫자로 표현이 되길래

잘 풀었다! 싶었는데 오답이란다

그래서 gpt한테 이런 문제 점화식 어떻게 찾냐 하니 동전 교환 문제와 같다 하더라

대체 이런 알고리즘들은 어떻게 알고 다 짜나 모르겠다.

그냥 많이 풀어보면서 익혀야하나...

 

이를 코드로 구현하면 다음과 같다.

import java.io.*;

public class N17626 {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());

        int[] dp =  new int[input + 1];
        dp[0] = 0;

        for (int i = 1; i <= input; i++) {
            int best = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                best = Math.min(best, dp[i - j * j] + 1);
            }
            dp[i] = best;
        }

        bw.write(String.valueOf(dp[input]));

        bw.flush();
        br.close();
        bw.close();
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.