백준 2293 동전 1(with Python)

어떤 문제?

제목에 쓰여 있는 문제입니다. DP(Dynamic Programming)를 활용하는 문제입니다.

내가 생각한 Solution

문제에서 생각해볼 점

• 일단 DP를 어떻게 설계할 것인지 생각해내야 하는데 절대적으로 생각이 나지 않아서 블로그를 참고하였습니다.

• 블로그 설명이 훌륭해서 DP 설계 방법은 이해했지만 처음에 메모리 사용량 초과가 발생했습니다. (크기 $100\cdot10000$ 배열 생성) $\rarr$ 메모리 초과

• 그래서 배열 크기를 줄여서 배열을 재활용하는 방법으로 접근했습니다. 하지만 시간 초과가 발생했습니다.

• 시간을 줄이기 위해서 아래와 같은 기능을 추가했습니다.

  • 총합이 최대 10,000이기 때문에 동전 한개의 가치가 10,000보다 큰 경우는 고려할 필요가 없습니다.

  • 만일 동전의 가치가 9,999 라면 9,999 이전에는 해당 동전을 사용할 수 없습니다. 따라서 1부터 9,998까지 경우의 수가 변하지 않을 것입니다.

• 아래 그림에서 어떻게 이해하고 설계 했는지 보여드리겠습니다.

• 위 그림처럼 직접 손으로 따라 써보면서 이해해보시는 것을 추천드립니다.

• 메모리 사용 공간을 줄이기위해 arr 크기를 $100\cdot10000\rarr1\cdot10000$ 줄이는 것과 계산 시간을 줄이기 위한 부분은 그다지 어렵지 않으므로 코드에 표시하겠습니다.

코드 구현

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

tmp_coins.sort()
coins = []
for coin in tmp_coins:
    if coin <= 10000:
        coins.append(coin)

arr = [0] * (k+1)

# 동전의 가치에 따라서 초기 배열을 설정
for i in range(coins[1], k+1, coins[1]):
    arr[i] = 1

arr[0] = 1

# 초기 배열 선언했으므로 2부터 시작
for r in range(2, len(coins)):
    # 시간을 줄이기 위해 코인의 가치랑 같은 값부터 갱신 시작
    for c in range(coins[r], k+1):
    	# 기존 경우의 수 값을 덮어 씌움으로 메모리 사용량 줄이기
        arr[c] = arr[c] + arr[c-coins[r]]

print(arr[-1])