거스름돈 계산하기 2

2024-09-26

#JAVA#프로그래머스

문제 설명

거스름돈 계산하기 2

정답률 34% · 제출 112회 · 예상 소요 시간 60분

곰돌이는 코드트리 마트에서 현재 일 하고 있습니다. 코드트리 마트에는 현재 N 가지의 동전들을 가지고 있고, 각 동전은 Ai 개를 가지고 있습니다.

곰돌이가 동전을 최소로 사용하여 거스름돈을 돌려주는 방법을 구하는 프로그램을 작성하세요.

입력 형식

첫번째 줄에 동전의 가지 수 N 과 돌려줘야 하는 거스름돈의 액수 S 가 공백을 사이에 두고 주어집니다.

두번째 줄부터 N 개의 줄에 걸쳐 각 동전의 가치 Vi 와, 가지고 있는 동전의 개수 Ai 가 공백을 사이에 두고 주어집니다.

단, 각 동전의 가치는 모두 다릅니다.

•
1 ≤ N ≤ 1,000

•
1 ≤ S ≤ 5,000

•
1 ≤ Vi ≤ 2,000

•
1 ≤ Ai ≤ 20

출력 형식

첫번째 줄에 곰돌이가 가장 적게 사용한 동전의 개수를 출력하세요. 만약 해당 거스름돈을 만들 수 없다면, -1을 출력하세요.

입출력 예제

예제1

입력:

5 21 1 1 2 3 3 4 4 5 5 2

출력:

5

예제2

입력:

2 20 3 2 9 3

출력:

1

문제 풀이 시간 : 1시간

문제 풀이 :

처음엔 그냥 되게 간단한 dp 문제인줄 알았는데

막상 풀려고 하니 dp를 어떤 식으로 코드를 짜야하는지 헷갈렸다.

초기 코드를 가져오고 싶은데

코드트리는 이미 지난 시험의 코드는 다시 볼 수 없는 것 같다.

그래서 기존 코드는 가져올 수 없지만

그냥 너무 생각을 깊게 했던게 독이 됐던 것 같다.

그래서 코드가 너무 더러웠고 복잡했다.

그래서 며칠 뒤에 다시 새로운 마음으로 문제를 봤더니 아주 간단한 문제라는 것을 알 수 있었다.

최종 코드

Java

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        int[] dp = new int[S+1]; //최소 거스름돈 수를 저장하는 dp 배열

        for(int i=1;i<=S;i++){ //0원일떄를 제외하고 모두 무한으로 설정
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int price = Integer.parseInt(st.nextToken()); //동전의 가격
            int count = Integer.parseInt(st.nextToken()); //동전을 가지고 있는 개수

            for(int j=0;j<=S;j++){ //0원부터 S원까지 반복
                if(dp[j]!=Integer.MAX_VALUE){ //현재 가격의 동전 개수가 무한이 아니라면
                    for(int k=1;k<=count;k++){ //동전의 개수만큼 반복
                        int idx = j+k*price; //다음 가격
                        if(idx>S){ //얻고자하는 가격을 넘으면 종료
                            break;
                        }
                        dp[idx] = Math.min(dp[idx],dp[j]+k); //원래 개수와 새로운 개수를 비교해서 최소값 저장
                    }
                }
            }
        }

        if(dp[S]==Integer.MAX_VALUE){ //해당 가격의 동전 개수가 무한이면 구할 수 없는 것
            System.out.println(-1);
        }
        else{ //구해져 있다면 출력
            System.out.println(dp[S]);
        }
    }
}