[백준] 동전 0 - 11047번

동전 0

1 초	256 MB	149950	80361	61355	52.637%

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1 복사

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 복사

6

예제 입력 2 복사

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2 복사

12

코드1

package 동전0;

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

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력을 받기 위해 BufferedReader를 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 첫 번째 줄에서 N과 K를 입력받음
        int N = Integer.parseInt(st.nextToken()); // 동전의 종류 수
        int K = Integer.parseInt(st.nextToken()); // 목표 금액

        // 동전의 종류를 저장할 배열 생성
        int[] coins = new int[N];
        for (int i = 0; i < N; i++) {
            // 각 동전의 가치를 입력받음
            coins[i] = Integer.parseInt(br.readLine());
        }

        int count = 0; // 필요한 동전의 총 개수

        // 가장 큰 동전부터 시작하여 금액 K를 맞추기 위한 반복문
        for (int i = N - 1; i >= 0; i--) {
            // 현재 동전이 목표 금액 K보다 크다면 넘어감
            if (coins[i] > K) continue;

            // 현재 동전으로 만들 수 있는 최대 개수를 더함
            count += (K / coins[i]);

            // 남은 금액을 계산
            K = K % coins[i];
        }

        // 결과 출력: 필요한 동전의 총 개수
        System.out.println(count);
        br.close();
    }
}

시간 복잡도

주어진 코드는 목표 금액을 만들기 위해 필요한 최소 동전 개수를 계산하는 프로그램입니다. 이 코드의 시간 복잡도를 분석해보겠습니다.

코드의 구조

1. 입력 처리:

   • BufferedReader와 StringTokenizer를 사용하여 입력을 처리합니다.
   • 첫 번째 줄에서 동전의 종류 수 N과 목표 금액 K를 입력받습니다.
   • 이 단계의 시간 복잡도는 O(1)입니다. (고정된 크기의 입력을 처리하는 경우)

2. 동전 배열 초기화:

   • N개의 동전 가치를 입력받아 coins 배열에 저장합니다.
   • 이 단계의 시간 복잡도는 O(N)입니다.

3. 동전 개수 계산:

   • 가장 큰 동전부터 작은 동전 순으로 목표 금액 K를 맞추기 위해 반복문을 수행합니다.
   • 동전의 종류 수는 N이고, 각 동전에 대해 K와 비교 및 나눗셈 연산을 수행합니다.
   • 이 단계의 시간 복잡도는 O(N)입니다.

4. 결과 출력:

   • 필요한 동전의 총 개수를 출력합니다.
   • 이 단계의 시간 복잡도는 O(1)입니다.

전체 시간 복잡도

위 단계를 종합하여 전체 시간 복잡도를 계산하면 다음과 같습니다:

• 입력 처리: O(1)
• 동전 배열 초기화: O(N)
• 동전 개수 계산: O(N)
• 결과 출력: O(1)

따라서, 주어진 코드의 전체 시간 복잡도는 O(N)입니다.

이 코드의 시간 복잡도는 동전의 종류 수 N에 선형적으로 비례합니다. 이는 매우 효율적이며, 동전의 종류가 많지 않은 경우(예: 수백 개 이하)에도 빠르게 동작할 수 있습니다. 🧑‍💻💡