코딩테스트 대비 문제 풀기

백준(02624) : 동전 바꿔주기

관련 알고리즘 : dfs(깊이 우선 탐색)

1. 입력받은 순서대로 사용하게 되는 동전의 가치를 Level로 간주
2. 종류별로 사용한 동전의 개수에 대해 각각의 경우에 발생하는 총 누적 금액을 각각의 노드로 간주
3. 루트 노드는 0원 (누적 금액이 없으므로)이고, 부모 노드에서 생성되는 자식 노드의 개수는 다음 Level에서 사용할 수 있는 동전의 가짓수가 됨. (예를 들어, 어떤 동전이 3개 있으면 간선의 개수는 4개가 됨)
4. 현재 동전의 개수를 결정하고 다음 동전으로 넘어가 그 동전의 개수를 결정하는 방식이 반복되기 때문에 DFS(깊이 우선 탐색)으로 코드를 구현.

코드 관련

■ Code 구현 설명

1. 누적 금액을 각각의 Node로, 초기 누적 금액 0원을 Root Node로
2. 입력한 동전의 순서대로 해당 동전을 사용하는 단계를 Level로
3. 해당 동전의 사용 개수만큼 자식 Node를 생성하여 간선으로 연결
   → 해당 Node의 순서가 해당 동전의 사용 개수를 의미
4. (자식 Node)는 (부모 Node)와 (해당 Level의 동전 × 간선의 가치(동전의 사용 개수))의 합을 의미
   → 단, 우리가 찾는 금액보다 Node가 큰 경우에는 해당 Node는 cut
5. 최하위 Level에서 우리가 찾는 금액을 확인 시, 카운트를 누적시켜서 최종적으로 카운트 값을 출력

■ Code 관련 파트별 풀이

1. 함수 선언
   
   

2. 필요한 값을 입력 받아 필요한 리스트 생성
   

3. 초기 카운트 지정 및 함수 호출, 결과 출력
   

최종 Code

	def dfs(L, total):			
	    global cnt			
	    if L == k:
	        if total == T:
	            cnt += 1		
				
	    else:			
	        for i in range(cn[L]+1):
	            dfs(L+1, total+(cv[L])*i)
				
	T = int(input())			
	k = int(input())			
				
	cv, cn = list(), list()			
				
	for i in range(k):			
	    a, b = map(int, input().split())			
	    cv.append(a)			
	    cn.append(b)			
				
	cnt = 0			
				
	dfs(0,0)			
				
	print(cnt)