문제
동전교환
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환
해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종
류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3
내 풀이(첫번째)
if __name__=="__main__":
n=int(input()) #동전 종류 개수
coin_list=list(map(int, input().split()))
m=int(input()) #거스름돈 액수
cnt=0
for i in range(1,n+1):
cnt+=m//coin_list[-i]
m=m%coin_list[-i]
if m==0:
break
print(cnt)
-DFS를 사용하지 않았다. 따라서 모든 경우를 고려해보지 못하므로 오류가 발생할 여지가 있다
두번째 풀이(=강의 답안)
def DFS(v, sum):
global result
if result<v:
return
if sum==m:
if result>v:
result=v
elif sum>m:
return
else:
for i in range(n):
DFS(v+1, sum+coin_list[i])
if __name__=="__main__":
result=2147000000
n=int(input())
coin_list=list(map(int, input().split()))
coin_list.reverse()
m=int(input())
DFS(0, 0)
print(result)
-지역 변수 처리
global result 코드를 통해서 전역 변수로 변환하여 처리하므로 local error를 해결했다.
-DFS처리
def DFS(v, sum): -->v:동전 개수 sum:그동안의 합계 금액
global result
if sum==m: -->코드 돌린 합계가 구하고자 한 거스름돈 총액과 동일할 때
if result>v:-->동전의 개수가 최소일 때를 구하는 것이 목적으므로
result=v 이전의 결과값보다 작을 때 결과값 업데이트
elif sum>m: --> 거스름돈 총액보다 커지면 의미가 없으므로 커트
return
else:
for i in range(n): -->DFS 돌리기
DFS(v+1, sum+coin_list[i])
-시간 초과 해결 코드
def DFS(v, sum):
global result
if result<v: -->result(이전의 동전 개수 최솟값)보다 v(동전 개수)가 많다면 더이상 코드를 돌릴 의미X
return
수열 추측하기 (0) | 2021.08.25 |
---|---|
순열 구하기 (0) | 2021.08.25 |
6.6 중복 순열 구하기(DFS) (0) | 2021.08.11 |
6.5 바둑이 승차(DFS) (0) | 2021.08.10 |
전역 변수와 지역 변수 (0) | 2021.08.10 |
댓글 영역