[백준] No.2294 - 동전 2 (C++, BFS구현)

문제

www.acmicpc.net/problem/2294

2294번: 동전 2

 

풀이

해당 문제는 다이나믹 프로그래밍 문제이다. 본인의 경우 여기에 BFS기법을 추가해서 문제를 해결했다.

 

일단 입력으로 받는 동전의 값이 10,000 이하의 수 일 때만 coin_value에 그 값을 저장한다. 가치의 합은 최대 10,000이기 때문에 그 이상의 값은 문제를 해결하는데 전혀 도움이 되지 않기 때문이다.

 

이후 coin_value를 정렬하고 BFS를 구현한다.

 

메모이제이션을 사용하기 위해 cache[10001] 배열에는 현재 가치의 합에 사용된 동전의 최소 개수를 저장한다.

 

BFS에서는 큐(sum_que)의 가장 앞(front)의 value를 sum_now에 저장하고 해당 값에서 모든 동전의 값들을 더해보며 cache[front value + sum_now]방문한다. 

 

만약 이미 방문했다면(-1이 아니라면) 해당 위치는 현재 호출한 위치보단 이전에 호출되었으므로 항상 더 작은 값을 가지고 있다. 따라서 해당 cache값이 -1이 아니라면 방문하지 않는다.

 

동전의 개수: 3, 가치 합: 15, 동전의 값: 1, 5, 12인 경우를 위와 같이 BFS로 구현하면 아래와 같이 cache값이 방문된다.

 

그림판이라 상태가 영 좋지 않습니다...

일단 파란색으로 둘러싸인 13을 확인해보자. 13은 BFS의 두 번째 깊이에서 방문이 된다. 동전의 값들은 정렬해 두었기 때문에 1로 인해 큐에 저장된 13이 먼저 방문된다. 즉, 가치 합 13원을 구성하는 최소 동전 개수는 2개이다. 

다음으로 12로 인해 큐에 저장된 13이 방문되는데 이미 같은 깊이에서 방문된 값(더 작거나 같은 값)이 저장되었기 때문에 더 이상 방문할 필요가 없다. 즉, 순서는 1+12, 12+1로 다르만 구성은 1과 12로 같기 때문에 방문하지 않는다.

 

가치 합 15원의 경우, 3번째 깊이와 4번째 깊이에서 방문된다. BFS에서 사용하는 큐는 항상 선입선출이기 때문에 5원을 3개 사용하는 경우가 1원 3개와 12원 1개를 사용하는 경우보다 항상 먼저 계산된다. 따라서 BFS로 구현할 경우 cache값에는 항상 최솟값만 저장되므로 값을 비교해줄 필요가 없다.

 

 

코드