[알고리즘] - 백준 2294번 : 동전2 (JAVA)

🎯 문제 : 동전 2

문제 풀러가기

🎯 입력, 출력

🚀 풀이 방법

1. 입력받은 k 길이 만큼의 배열을 Integer.MAX_VALUE로 초기화.

   • 배열을 k길이만큼 만드는 이유는 배열의 인덱스를 입력받은 동전으로 만들어야 하는 가치라고 생각하기 위해
     ex) dp[3]은 3의 가치를 만들어 내기 위한 동전의 개수를 의미 하도록!

2. 입력 받은 동전의 가치를 활용해 순차적으로 dp의 최소 값을 계속해서 갱신 해 나가면 된다!
   ex)
   문제에서 동전의 가치가 1인 것만을 입력 받았을 때에는
   dp[5]=5 일 것입니다. (1의 가치가 5개가 모여야 하니)
   이제 동전의 가치가 5인 것도 입력을 받고 나면?!
   dp[5]=1 로 갱신 될 것입니다!

   이렇게 순차적으로 갱신해 나가면 이 문제는 끝입니다!

[도출된 점화식]

dp[n]=min(dp[n],dp[n-동전의 가치]+1)

유의 사항 😥

1. dp[0]=0입니다.
   도출된 점화식을 활용해야 하기 때문!
2. dp[k]=Integer.MAX_VALUE이면 -1을 출력 해야 합니다.
   k의 가치를 입력받은 동전으로 만들 수 없다는 것을 뜻하기 때문 입니다!

🚀 CODE

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n,k;
    static int[] arr;

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine()," ");
        n=Integer.parseInt(st.nextToken());
        k=Integer.parseInt(st.nextToken());
        arr=new int[n+1];

        for(int i=1;i<=n;i++)
        {
            st=new StringTokenizer(br.readLine());
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        int[] dp=new int[k+1];

        for(int i=1;i<=k;i++){
            dp[i]=Integer.MAX_VALUE-1;
        }
        for(int i=1;i<=n;i++){
            for(int j=arr[i];j<=k;j++){
                dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
            }
        }

        if(dp[k]==Integer.MAX_VALUE-1)
            System.out.println(-1);
        else
            System.out.println(dp[k]);
    }

}

👏 정답!

😍 이상으로 포스팅을 마치겠습니다. 감사합니다:)