코딩테스트 : 동전 1

문제

동전 1

n가지 종류의 동전이 있습니다. 각각의 동전이 나타내는 가치는 다르며, 이 동전들을 적당히 사용해서 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 프로그램을 작성하세요.

각각의 동전은 몇 개라도 사용할 수 있으며, 사용한 동전의 구성이 같은데 순서만 다른 것은 같은 경우로 취급합니다.

입력 형식

1. 첫째 줄에 두 개의 정수 n과 k가 주어집니다.
   • n: 동전의 종류 개수 (1 ≤ n ≤ 100)
   • k: 만들어야 하는 금액 (1 ≤ k ≤ 10,000)
2. 다음 n개의 줄에는 각각의 동전의 가치가 주어집니다.
   • 각 동전의 가치는 100,000보다 작거나 같은 자연수입니다.

출력 형식

1. 첫째 줄에 경우의 수를 출력합니다.
   • 경우의 수는 2^31보다 작습니다.

입출력 예

예제 입력 1

3 10
1
2
5

예제 출력 1

10

문제 유형 분류

• 전형적인 동전 조합의 수를 구하는 동적 계획법(DP) 문제
• 중복 순서는 허용하지 않으므로 조합(combination)을 구하는 문제
• 각 동전은 무한히 사용할 수 있으므로 완전 탐색보다는 DP로 누적해서 처리

시간 복잡도 + 공간복잡도 추정

• 시간복잡도: $O(n * k)$ (각 동전에 대해 1원부터 k원까지 반복)
  
• 공간복잡도: $O(k)$ (1차원 dp 배열 사용)
  

적합한 알고리즘 / 자료구조

• DP (Dynamic Programming)
• dp[i]: i원을 만드는 경우의 수

필요한 라이브러리

최악의 경우 시뮬레이션

접근 방법

1. dp[0] = 1로 초기화

   • 0원을 만드는 경우는 “동전을 하나도 사용하지 않는 방법” 1가지

2. 각 동전에 대해

   for coin in coins:
   	for i in range(coin, k + 1):
   		dp[i] += dp[i - coin]

   • 현재 금액 i원을 만들기 위해 coin을 추가했을 때, i - coin원을 만들 수 있는 경우의 수를 더함.
   • dp[i] += dp[i - coin] → i - coin원을 만들 수 있다면 거기에 coin을 하나 더해서 i원을 만들 수 있다는 의미
     
   • 동전 종류를 바깥 루프로 돌면 순서가 다른 구성은 중복으로 세지 않게 됩니다.

최종 코드

Ver 1

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dp = [0] * (k + 1)
dp[0] = 1  # 0원을 만드는 경우는 1가지

for coin in coins:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

print(dp[k])

Ver 2

def count_coin_cases(n, k, coins):
    dp = [0] * (k + 1)
    dp[0] = 1  # 0원을 만드는 경우는 1가지 (아무 동전도 사용하지 않음)

    for coin in coins:
        for j in range(coin, k + 1):
            dp[j] += dp[j - coin]  # 현재 동전을 사용하는 경우의 수 추가

    return dp[k]  # k원을 만드는 모든 경우의 수 반환

# 입력 처리
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

print(count_coin_cases(n, k, coins))