코테 연습) 다이나믹 프로그래밍 : 피보나치 수열(문제 : 효율적인 화폐 구성).python

 

 

q3) 효율적인 화폐 구성

- N가지 종류의 화폐가 있다 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다 이때 각 종류의 화폐는 몇 개라도 사용할 수 있다.

- 예를들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다

- M원을 만들기 위한 최소한의 화폐 개수를 출력

 

 ex) N가지 화폐의 N을 2로 M원이 되도록의 M을 15로 그리고 화폐의 단위는 2, 3으로 입력 받았을때의 예시로 보면

2 15

2

3

에서 출력은 5가 된다 

하지만 여기서 문제조건에 또 다른 경우의 수를 두었다 불가능 할 때는 -1을 출력 이라는 조건이 붙었다!

이 점을 유념하자

 

 - a¡ = 금액 i를 만들 수 있는 최소한의 화폐 개수

 - k = 각 화폐의 단위

 - 점화식 : 각 화폐 단위인 k를 하나씩 확인하며

 - 다시 다른 예시로 들어보자

 N = 3, M =7이고 각 화폐의 단위가 2, 3, 5인 경우

    - 먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정 

    - INF은 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않는다는 의미를 가진다

    - 본 문제에서는 조건에 의해 10,001을 사용할 수 있다

[step 0] (초기화)

 

 

    - 첫 번째 화폐 단위인 2를 확인한다

    - 점화식에 따라서 다음과 같이 리스트가 갱신된다

[step 1]

 

 

    - 두 번째 화폐 단위인 3를 확인한다

    - 점화식에 따라서 다음과 같이 리스트가 갱신된다

[step 2]

 

 

 

    - 세 번째 화폐 단위인 5를 확인한다

    - 점화식에 따라서 다음과 같이 최종적으로 리스트가 갱신된다

[step 3]

 

 

->입력창

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i -k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계사된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

 

->출력창 N= 3, M= 7 입력 엔터 후 화폐단위 2 엔터 3엔터 5 엔터 해서 출력값 2

C:\Users\admin\PycharmProjects\ML_EX\venv\Scripts\python.exe C:/Users/admin/PycharmProjects/ML_EX/study06.py
3 7
2
3
5
2

종료 코드 0(으)로 완료된 프로세스

 

 

풀이)

 

# 정수 N, M을 입력 받기
n, m = map(int, input().split())

- n, m을 띄어쓰기 기준으로 입력 받고 정수로 바꾸기

# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

- 빈 리스트에 입력받은 n값을 넣어라

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

- 조건에 제시된 10000을 넘는 10001으로 초기화시키면 INF(무한)가 형성 (조건에 따랐을 때)

- 입력받은 0 부터 m원까지의 DP 테이블을 10001로 초기화

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0

- DP테이블의 첫번째 원소는 0으로 설정

for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i -k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

- 입력 받은 화폐 개수의 길이 - 1만큼 인덱스 값을 0부터 차례로 꺼낸값을 i라고 하고 아래 반복

- 방금 꺼낸 i값의 숫자에 해당하는 array의 인덱스번호에 해당하는값에서부터 m원의 범위까지 꺼낸 차례로 꺼낸 값을 j라고 하고 아래 반복

- 만약 d[j에 해당ㅎ아는 DP테이블의 인덱스 번호에 해당하는 값 - array의 i번째 인덱스 번호에 해당하는 값]이 10001이 아니라면 다음을 수행

- d[j값에 해당하는 DP테이블의 인덱스번호에 해당하는 값] = 최소값(j값에 해당하는 DP테이블의 인덱스번호에 해당하는 값,  (j값에 해당하는 DP테이블의 인덱스번호에 해당하는 값 - array의 i번째 인덱스 번호에 해당하는 값) +1)

 

n= 3, m = 7 화폐 단위로 2 3 5를입력받았을 때

array 인덱스 = i	인덱스0	인덱스1	인덱스2
화폐단위	2	3	5

DP테이블	인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7
초기화	0	10001	10001	10001	10001	10001	10001	10001
i = 0, j = 2	0	10001	1 갱신	10001	10001	10001	10001	10001
i = 0, j = 3	False	False	False	False	False	False	False	False
i = 0, j = 4	0	10001	1 유지	10001	2 갱신	10001	10001	10001
i = 0, j = 5	False	False	False	False	False	False	False	False
i = 0, j = 6	0	10001	1 유지	10001	2 유지	10001	3 갱신	10001
i = 0, j = 7	False	False	False	False	False	False	False	False
	0	10001	1	10001	2	10001	3	10001

DP테이블	인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7
	0	10001	1	10001	2	10001	3	10001
i = 1, j = 3	0	10001	1 유지	1 갱신	2 유지	10001	3 유지	10001
i = 1, j = 4	False	False	False	False	False	False	False	False
i = 1, j = 5	0	10001	1 유지	1 유지	2 유지	2 갱신	3 유지	10001
i = 1, j = 6	0	False	1 유지	1 유지	2 유지	2 유지	2 갱신	10001
i = 1, j = 7	0	10001	1 유지	1 유지	2 유지	2 유지	2 유지	3 갱신

DP테이블	인덱스0	인덱스1	인덱스2	인덱스3	인덱스4	인덱스5	인덱스6	인덱스7
	0	10001	1	1	2	2	2	3
i = 2, j = 5	0	10001	1 유지	1 유지	2 유지	2 유지	2 유지	3 유지
i = 2, j = 6	False	False	False	False	False	False	False	False
i = 2, j = 7	0	10001	1 유지	1 유지	2 유지	2 유지	2 유지	2 갱신

- 반복문을 풀어써보면 위와 같다 False인 경우 위의 결과를 그대로 가져온다 

- i = 1, j = 7에서 이미 값이 나왔지만 n이 끝날때까지 반복문을 계속 돌린결과  i = 2, j =7에서 더 작은 값이 나와서 갱신되었다 이 결과는

 

- i = 2인 array[2]= 5 (첫번째 표를 보면 array의 인덱스번호 2의 값은 5) , j = 7

- for i in range(n): # n은 3을 입력받았으니 range함수로 인해 0부터 2까지 반복이므로 i = 2가 마지막 반복
    for j in range(array[i], m + 1): # 위에서 현재 i = 2인 상황을 하고 있으니 (array[i], m + 1)는 array[5], 입력받은 m값인 7

                                                   # range함수는 번위에서 끝에값 -1 을 해주니 결국 +1과 -1이 되어 범위는 m까지인 7까지

                                                   # 그럼 범위는 5부터 7까지가 되는거고

                                                   # 위에 마지막 표에서 보면 i = 2, j = 7인 경우에서 2로 갱신된 경우를 풀어보자면

        if d[j - array[i]] != 10001: # 만약 d[7 - 5] != 10001 즉 d[2]가 10001이 아니라면 아래 식 실행

                                               # i =2, j = 7의 전 단계인 i = 2, j = 6에서보면 False는 위의 값 그대로니까 d[2]= 1이므로 True

            d[j] = min(d[j], d[j - array[i]] + 1) # d[7] = min(d[7], (d[7 -5] +1))는 i = 2, j = 6에서 보면 False라 위의 값 그대로 가져온거 봤을 때 d[7] = 3, d[2] = 1 이므로 d[7] = min(3, 1+1)) 최솟값을 선택하는거니까 d[7]=2가 된다

 

 

# 계사된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

- j[7]이 10001이 아니니까 else로 넘어가고 d[7]현재 값인 2를 출력 해당 2는 n의 입력값중에 2와 5를 합한 값 

 

 

 

출처 / 유튜브 [동빈나 - (이코테2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬]