[자바]백준 9625번

by

안녕하세요. 개발자 움탱입니다.
이 기사는 알고리즘을 공부하면서 공부를 추적하기 위한 것입니다.
그래서 설명마다 일기장으로 편하게 쓰려고 하고 짧은 언어 형식으로 쓰려고 합니다.
그리고 더 좋은 시각이 있으시거나 잘 모르시는 부분이 있으시면 알려주시면 정말 감사하겠습니다.
좋은 하루 보내세요 🙂

문제

Chunhyang은 슈퍼마켓 카운터에서 일합니다.

고객이 2원권과 5원권만 거스름돈을 요구합니다. 당신은 무한한 수의 2코인과 5코인을 가지고 있습니다. 동전의 수는 최소한으로 줄여야 합니다. 변화량이 n일 때 동전의 최소 개수를 알려주는 프로그램을 작성하세요.

'추천 관련글,

예를 들어 거스름돈이 15원이면 5원짜리 3개, 14원이면 5원짜리 2개와 2원짜리 2개를 받아 총 4개가 된다. 동전의 수를 최소화하기 위해 총 5개를 줍니다.

기입

첫 번째 줄은 청구 금액 n(1 ≤ n ≤ 100,000)을 지정합니다.

누르다

최소 변경량을 인쇄합니다. 실행 취소할 수 없으면 -1을 인쇄합니다.

예


예

알고리즘 분류

  • 수학
  • 동적 프로그래밍
  • 그리디 알고리즘

문제

위의 문제 설명은 간단합니다.

5개의 원과 2개의 원만 있는 최소한의 원으로 주어진 n-circle을 만들기 위한 최소 요소 수를 찾으십시오.

논평

5원이라는 숫자만 구하고 남은 금액을 2원으로 계산할 수 있다고 생각하면 다음과 같은 이유로 오산이다.

  • n = 16이라고 하자
  • 5원을 먼저 계산하면 3 5원으로 15원을 만들고 1원이 남는다.
  • 1원을 2원으로 계산하려 하면 안 된다.

동그라미 1부터 동그라미 n까지 순서대로 가장 작은 수를 찾으세요.

왜? 모두 순서대로 저장해야 하나요?

16원으로 예를 들어보겠습니다.

  • 5 + 5 + 2 + 2 + 2
  • 2 + 2 + 2 + 2 + 2 + 2
  • 5 + 5 + 5 + 2 (엑스)

이렇게 하면 하나씩 저장할 수 있습니다. 그러나 n이 100,000이면 개별적으로 얻을 수 있습니까?

그러면 시간 복잡도가 제한 시간을 초과합니다.

그렇다면 방법은 하나뿐이다 반대 방법 사용해야한다.

  1. 16원이면 최소 14원 또는 9원에 1을 더하면 됩니다.
  2. 그렇다면 최소값 14원과 최소값 9원은 어떻게 아는 걸까요?
  3. 따라서 첫 번째부터 n번째까지의 최소값을 구하고, 마지막 n번째의 최소값을 구한다.

졸업 증서

n의 원에서 2와 5의 조합의 최소 수는

  1. (n – 2) 원의 최소 조합 수
  2. (n – 5) 원의 최소 조합 수

둘 중 가장 작은 것에 1을 더하면 n의 최소 조합 수가 제공됩니다.

말로 설명하긴 어렵지만 나중에 사진 찍어서 첨부할게요.

지금 바로 코드를 살펴보겠습니다.

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

public class Main {
    public static void main(String() args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int LNF = Integer.MAX_VALUE;

        int n = Integer.parseInt(br.readLine());

        int() arr = new int(n + 1 + 6);
        arr(0) = LNF;
        arr(1) = LNF;
        arr(2) = 1;
        arr(3) = LNF;
        arr(4) = 2;
        arr(5) = 1;

        for (int i = 6; i < arr.length; i++) {
            arr(i) = Math.min(arr(i - 2), arr(i - 5)) + 1;
        }

        System.out.println(arr(n) == LNF ? -1 : arr(n));
        br.close();
    }
}

코드 설명

꼭 필요한 부분만 설명하겠습니다.

arr 배열의 길이가 n+1+6인 이유

  1. 물론 n+1은 n을 찾아야 하므로 n+1로 표현해야 한다.
  2. +6으로 한 이유는 0부터 5까지의 값을 직접 입력하기 위함인데 n=1이고 길이를 n+1로 하면 길이가 2가 되어 에러가 난다. 따라서 오류 발생을 방지하기 위해 0에서 5까지의 길이를 미리 추가합니다.
  3. 어쨌든 n번째 값만 찾으면 되므로 n 6개 이상의 최소값을 찾는 것은 중요하지 않습니다.

0, 1, 3을 MAX_VALUE로 설정하고 2, 4, 5에 대해 서로 다른 값을 설정한 이유

  • 0, 1, 3은 번호를 얻을 수 없었기 때문에 LNF로 입력되었습니다.
  • 문제를 해결할 수 없으면 -1을 인쇄하라는 메시지가 표시됩니다. 그래서 -1을 입력하면 아래와 같이 조건문이 추가되어 조금 복잡해집니다.
for (int i = 6; i < arr.length; i++) {
	// 조건문을 해주지 않으면 -1이 최소값이 -1 + 1 = 0이 출력된다.
	if (arr(i - 2) == - 1) { 
    	arr(i) = arr(i - 5) + 1;
    } else if (arr(i - 5) == - 1) {
    	arr(i) = arr(i - 2) + 1;
    } else {
    	arr(i) = Math.min(arr(i - 2), arr(i - 5)) + 1;
    }
}
  • 2, 4 및 5는 달성 가능한 최소값입니다.