[자바] 백준 22839 - Square Coins (java)

목차

문제 : boj22839

 

 

필요 알고리즘

• 동적 계획법 (DP), 배낭 문제 (냅색)
  
  • 유명한 DP 유형인 냅색으로 해결할 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 살펴봐야 할 것이, 입력값의 최대치는 300이고, coin의 최대치는 17x17 이라는 점이다. 그리고 테스트케이스가 여러개 있긴하지만 어차피 300까지 모두 구해두면 각 테스트 케이스는 O(1)로 구할 수 있다.

 

  따라서 1원부터 300원까지 1x1~17x17 짜리 동전을 가지고 가능한 경우의수를 모두 구해두자!

여기까지만 보면 dp[n]을 n원을 만들 수 있는 경우의 수로 정의하면 될 것 같긴한데, 주의할점은 동전의 순서가 달라도 구성이 동일하면 동일한 경우로 쳐야한다는 점이다. 즉, 1원짜리 3개와 4원짜리 1개 == 1원짜리 2개와 4원짜리 1개와 1원짜리 1개이다.

 

  따라서 dp[n][a] 를 n원을 만들 때, 마지막으로 사용한 동전이 a*a원인 경우로 정의하자. 그렇다면 dp[n][a] = dp[n-a*a][1] + dp[n-a*a][2] + ... + dp[n-a*a][a] 라 할 수 있다. 즉, 현재 살펴보고 있는 동전이 a*a원일 경우 그 이전에 a원보다 작은 금액으로 계산한 결과만 포함하는 것이다. 이런식으로 하면 말로 설명해봤을 때, '1*1원 + 1*1원 + 2*2원 + 4*4원' 이런식으로 항상 증가하거나 동일한 순서대로만 동전의 조합을 배치를 할 수 있어서 순서만 다른 경우를 배제할 수 있다. 코드에서 dp 배열이 위에서 설명한 내용을 계산하는 부분이다. result는 이후 각 테스트케이스를 빠르게 계산하기 위해 미리 1차원으로 답을 구해둔 배열이다. 최종적으로 시간복잡도는 O(테스트케이스 수 + 300*17*17) 이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int[] dp = getDp();

        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;


            sb.append(dp[n]).append('\n');
        }
        System.out.print(sb);
    }

    private int[] getDp() {
        int[][] dp = new int[301][18];
        int[] result = new int[301];
        dp[0][0] = 1;

        for (int i = 1; i <= 300; i++) {
            for (int c = 1; c <= 17; c++) {
                int square = c*c;
                if (i - square < 0) break;

                for (int j = 0; j <= c; j++) {
                    dp[i][c] += dp[i-square][j];
                }
            }

            for (int j = 1; j <= 17; j++) {
                result[i] += dp[i][j];
            }
        }

        return result;
    }
}