📙[Algo] 24.05.01 알고리즘

알고리즘 문제) BOJ 2294. 동전 2

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

문제 요약

• N가지 동전 존재
• 동전을 적당히 사용해서 가치의 합이 K원이 되도록 함
  • 각각의 동전은 몇 개라도 사용할 수 있다
• 이때, 동전 개수의 최솟값을 구하시오

시간 제한

• 1초

입력

• N, K
  • 1 ≤ N ≤ 100, 1 ≤ K ≤ 10000
• N개의 줄에 동전의 가치가 주어짐
  • 동전의 가치는 10만 이하 자연수
  • 가치가 같은 동전이 여러 번 주어질 수 있음

출력

• 사용한 동전의 최소 개수 출력
  • 불가능한 경우 -1 출력

접근법

• 각 동전마다 선택O, 선택X ⇒ 2가지 경우가 존재
  • N이 최대 100가지 존재할 수 있으므로,
  • 22….*2 = $2^{100}$가지가 되므로, 단순 완탐은 시간초과 뜸.
  • 또한, 각각의 동전은 중복해서 사용할 수 있다는 조건이 존재한다.
• 결국 최적화가 필요한 문제 ⇒ Top Down DP로 접근
  • 우선 백트랙킹으로 작성(cur : 현재 가리키는 동전, total : 선택한 동전 가치 총합)
    • 가지치기로 가치 total이 K가 넘어가면 가장 큰 값을 return한다. (정답이 되지 못 하도록)
    • 또는 cur이 존재하는 동전 가짓수를 넘어가는 경우에도 가장 큰 값을 return 한다.
    • 만약 total이 K가 된다면 return 0을 한다. → 가능한 경우라는 뜻
    • 재귀로 넘겨줄 때 선택한 경우 + 1하고, 아닌 경우는 + 0인데, 이때의 반환값들 중 최솟값을 return 한다.
  • 그다음 메모이제이션으로 dp[cur][total]에 기록

코드

• 합을 더해가는 방법

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

public class Main {
    static int N, K;
    static int[] price;
    static int[][] dp;

    static int backtracking(int cur, int total) {
        // cur : 현재 가리키는 동전
        // total : 선택한 동전 가치 총 합

        // 가치를 초과하는 경우는 최댓값 반환 -> 정답으로 선택되면 안 되므로
        if (total > K || cur >= N) return 1 << 30;

        if (total == K) return 0;

        if (dp[cur][total] != -1) return dp[cur][total];

        // 현재 동전만 선택 또는 동전 선택 안하고 다음 동전으로 넘어가는 경우
        int ret = Math.min(backtracking(cur, total + price[cur]) + 1,
                backtracking(cur + 1, total));

        dp[cur][total] = ret;
        return dp[cur][total];
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        price = new int[N];
        for (int i = 0; i < N; i++) {
            price[i] = Integer.parseInt(br.readLine());
        }

        dp = new int[110][10010];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }

        int answer = backtracking(0, 0);
        if (answer == 1 << 30) bw.write("-1");
        else bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

• 합을 빼가는 방법

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

public class Main {
    static int N, K;
    static int[] price;
    static int[][] dp;

    static int backtracking(int cur, int total) {
        // cur : 현재 가리키는 동전
        // total : 남은 가치 합

        // 가치를 초과하는 경우는 최댓값 반환 -> 정답으로 선택되면 안 되므로
        if (total < 0 || cur >= N) return 1 << 30;

        if (total == 0) return 0;

        if (dp[cur][total] != -1) return dp[cur][total];

        // 현재 동전만 선택 또는 동전 선택 안하고 다음 동전으로 넘어가는 경우
        int ret = Math.min(backtracking(cur, total - price[cur]) + 1,
                backtracking(cur + 1, total));

        dp[cur][total] = ret;
        return dp[cur][total];
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        price = new int[N];
        for (int i = 0; i < N; i++) {
            price[i] = Integer.parseInt(br.readLine());
        }

        dp = new int[110][10010];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }

        int answer = backtracking(0, K);
        if (answer == 1 << 30) bw.write("-1");
        else bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}