선생님 섹션 8의 9번 동전교환 문제를 복습하면서 풀어보니 손에 익어서 이젠 풀 수 있게 되었습니다. 여기서 문제를 변형시켜서 가장 적은 동전갯수를 반환하는게 아닌, 가장 작은 동전 갯수를 가진 동전 종류의 배열 (해당 문제의 경우 [5,5,5])를 반환하도록 문제를 풀고있는 중인데요. 간단할 거 같았는데 의외로 잘 안풀리네요 ㅠㅠ 출력해보면서 이리저리 해보는데 접근 방법과 풀이를 알려주실 수 있을지 여쭙습니다. 아래는 여태 작성한 제 코드입니다. let answer = Number.MAX_SAFE_INTEGER let len = arr.length let tmp = [] function DFS(L , sum){ if (sum > m) return if (L > answer) return if (sum === m) { answer = Math.min(answer, L) console.log(answer) console.log(tmp) tmp = [] } else { for (let i=0; i<len; i++){ DFS(L+1 , sum+arr[i]) if (!tmp.length || tmp.reduce((a,b)=>a+b) <= m) tmp.push(arr[i]) } } } DFS(0, 0) return answer } let arr=[1, 2, 5]; console.log(solution(15, arr));
안녕하세요 강사님, 강의를 듣다가 동전 문제를 BFS로 풀 수 있을거 같아 이렇게 풀었는데, 괜찮은 코드인지 여쭤보고 싶습니다. import java.io.BufferedReader ; import java.io.InputStreamReader ; import java.util.* ; public class Main { static int N , M , count ; static int [] arr ; static Queue<Integer> queue = new LinkedList<>() ; public void input () throws Exception { BufferedReader br = new BufferedReader( new InputStreamReader(System. in )) ; StringTokenizer st = new StringTokenizer(br.readLine()) ; N = Integer. parseInt (st.nextToken()) ; arr = new int [ N ] ; st = new StringTokenizer(br.readLine()) ; for ( int i = 0 ; i < N ; i++) { arr [i] = Integer. parseInt (st.nextToken()) ; queue .offer( arr [i]) ; } st = new StringTokenizer(br.readLine()) ; M = Integer. parseInt (st.nextToken()) ; } public int BFS () { while (! queue .isEmpty()) { count ++ ; int len = queue .size() ; for ( int i = 0 ; i < len ; i++) { int value = queue .poll() ; for ( int X : arr ) { int data = value + X ; if (data == M ) return count + 1 ; // 동전의 값을 Queue 에 삽입 전에 체크하기 때문에 +1 를 추가해서 리턴 if (data < M ) queue .offer(data) ; } } } return count ; } public static void main (String[] args) throws Exception { Main main = new Main() ; main.input() ; System. out .println(main.BFS()) ; } }
