일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 투포인터
- dfs
- useAppDispatch
- app router
- 리터럴 타입
- 인터섹션
- map
- Cypress
- 결정 알고리즘
- 타입 좁히기
- tailwind
- CORS
- Promise
- TS
- recoil
- autosize
- SSR
- 공변성
- webpack
- 무한 스크롤
- async/await
- 태그된 유니온
- CI/CD
- RTK Query
- React
- Jest
- ESlint
- 이분 검색
- 반공변성
- 호이스팅
Archives
- Today
- Total
짧은코딩
동전교환(DFS) 본문
코드
function solution(m, arr) {
let answer = Number.MAX_SAFE_INTEGER;
let n = arr.length;
function DFS(L, sum) {
if (sum > m) return;
if (L >= answer) return;
if (sum === m) {
answer = Math.min(answer, L);
} else {
for (let i = 0; i < n; i++) {
DFS(L + 1, sum + arr[i]);
}
}
}
DFS(0, 0);
return answer;
}
풀이
이 문제는 DFS(L, sum)으로 해서 풀어야한다. 여기서 L은 동전의 개수이고 sum은 값의 합이다.
위 사진처럼 가지를 뻗어 가면서 돌아가도록 해야한다. 그러다가 sum이 거스름 돈보다 크거나 L이 answer보다 커지면 가지 뻗는 것일 종료해야 한다. 이를 구현한 것이 위 코드이다.
728x90
반응형
'코딩테스트 with JS > 자바스크립트 알고리즘 문제풀이(인프런)' 카테고리의 다른 글
수열 추측하기 (0) | 2022.12.24 |
---|---|
조합의 경우수(메모이제이션) (0) | 2022.12.23 |
부분집합 구하기(DFS) (0) | 2022.12.18 |
마구간 정하기(결정 알고리즘), 이분검색 (0) | 2022.12.15 |
뮤직비디오(결정 알고리즘), 이분검색 (0) | 2022.12.13 |
Comments