[Baekjoon] 26934_The Bus Card

문제(출처: https://www.acmicpc.net/problem/26934)

---

< The Bus Card >

 

문제 풀이 

 

dp를 사용하여 100, 200, 500 단위로 충전하여 충전 횟수를 최소화한 값을 구한다. 

 

my solution (Java)

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

public class _26934_ { // The Bus Card

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int k = Integer.parseInt(bf.readLine());

		int arr[] = new int[10001];
		int coins[] = { 100, 200, 500 };

		for (int i = 1; i < 10001; i++) {
			for (int j = 0; j < 3; j++) {
				if (i % 100 == 0 && i - coins[j] >= 0) {
					if (arr[i] == 0) {
						arr[i] = arr[i - coins[j]] + 1;
					} else {
						arr[i] = Math.min(arr[i], arr[i - coins[j]] + 1);
					}
				}
			}
		}

		if (arr[k] == 0) {
			for (int i = k; i < 10001; i++) {
				if (arr[i] > 0) {
					System.out.println(arr[i]);
					break;
				}
			}
		} else {
			System.out.println(arr[k]);
		}
	}
}

변수)
k : 충전할 양
arr : 각 돈만큼 충전 횟수 
coins : 충전 가능한 단위

 

충전할 양을 입력받는다. 최대 값인 10000만큼 살펴보며 충전 횟수를 최소로 하는 값을 구한다. 만약 100으로 나누어 떨어지고, 현재 값 - 충전 가능한 단위 값이 0 이상이라면 최소 횟수로 업데이트한다. 

 

만약 arr[k] 값이 0이라면 나누어 떨어지지 않아 많이 충전해야 하므로 k보다 큰 값 중에서 arr[i] 값이 0보다 클 때 출력한다. arr[k] 값이 0이 아니라면 그 값을 출력한다. 

---

---