[BOJ] BOJ 17626번 'Four Squares' (Java)

[문제]

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

 

[접근방식]

문제를 보자마자 든 생각은

'동전' - https://notorious.tistory.com/412

'동전2' - https://notorious.tistory.com/414

위 두문제와 유사한 방식으로 해결해야 겠다 였다.

 

위 두 문제는 동전 종류를 하나씩 대입하여 dp[i] = dp[i - coin] + 1 방식을 통해, i원을 구성하는 경우의 수 개수를 구하는 해결 방식을 채택했다.

 

이와 비슷하게 "동전의 종류" 대신에 제곱(1^2, 2^2, 3^3, ...)를 대입하여 해결하고자 하였다.

 

dp배열의 정의는 "i 를 표현하는 제곱수들의 최소 개수" 로 설정하였다.

 

[Java 코드]

/**
 * BOJ_17626 Four Squares
 * https://www.acmicpc.net/problem/17626
 * keyword - 
 */

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());

    //DP 정의 : i 를 표현하는 제곱수들의 최소 개수
    int[] dp = new int[n + 1];

    for (int i = 1; i <= n; i++) {
      dp[i] = i; //최악의 경우 :  1^2로만 구성
      for (int k = 1; k * k <= i; k++) {
        dp[i] = Math.min(dp[i], dp[i - k * k] + 1);
      }
    }

    //dp[n] 출력
    System.out.println(dp[n]);
  }
}

 

[Rewind]

1. 어려웠던 점

- 이 문제는 '접근방식'을 문제를 접하자마자 알고 있었다.

- 그러나, 구현과정에서 너무나 어렵게 생각하여 스스로 문제해결에서 멀어졌다.

- 그러자 아래와 같은 기괴한 코드가 나오게 되었다.

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 INF = 50_001;

    //DP 정의 : i 를 표현하는 제곱수들의 최소 개수
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      dp[i] = i; //최악의 경우 1^2로 모두 채우는 경우
    }
    
    for (int k = (int) Math.sqrt(n); k >= 1; k--) {
      for (int i = k * k; i <= n; i++) {
        if (i + K * k <= n) {
          dp[i] = Math.min(dp[i], dp[i + k * k] + 1);
        }
      }
    }

    //dp[n] 출력
    System.out.println(dp[n]);
  }
}

- 위 코드의 문제점은 다음과 같다.

 

- 1. dp 원소의 초기화 실패

 : 1 <= i <= n 인 자연수 i 를 구성하는 제곱근 수의 최악의 경우는 1^2로만 구성되는 것이다. 즉, 'i' 이다.

따라서, n의 최댓값 50,000 에 1을 더한 수인 'INF'로 초기화할 필요가 없이, dp[i]의 초기화값은 i 이다.  

 

- 2. 어처구니 없는 DP 구현 방식 (반복문 설정)

 : '동전' , '동전2' 문제와 같이 가장 바깥쪽 반복문에 '제곱수'의 제곱근를 의미하는 'k' 값을 배치하는 것에 매몰되어 본질을 잃게 되었다.

단순히, 가장 바깥쪽 반복문엔 "1 ~ n" 의 수를 놓았으면 됐다.

안쪽 반복문엔 k 를 배치하고 k * k <= i 를 조건으로 놓았으면 됐다.

 

2. 알게된 점

- 아직 많이 많이 부족하다는 것을 알게되었다.

- 쉬워보이는 문제를 스스로 해결하지 못해 상당히 아쉽고 실망했다.

 

3. 개선방안

- 잘 모르겠음.