๋ฌธ์ ๋งํฌ
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํ๊ฒ ๋๋ฒ
n๊ฐ์ ์์ด ์๋ ์ ์๋ค์ด ์์ต๋๋ค. ์ด ์ ์๋ค์ ์์๋ฅผ ๋ฐ๊พธ์ง ์๊ณ ์ ์ ํ ๋ํ๊ฑฐ๋ ๋นผ์ ํ๊ฒ ๋๋ฒ๋ฅผ ๋ง๋ค๋ ค๊ณ ํฉ๋๋ค. ์๋ฅผ ๋ค์ด [1, 1, 1, 1, 1]๋ก ์ซ์ 3์ ๋ง๋ค๋ ค๋ฉด ๋ค์ ๋ค์ฏ ๋ฐฉ๋ฒ์ ์ธ ์
programmers.co.kr
์ ๊ทผ ๋ฐฉ๋ฒ
์์ ํ์ ๋ฌธ์ ๋ก dfs(๊น์ด ์ฐ์ ํ์) ๋ฐฉ์์ผ๋ก ์งํํ์๋ค.
์ฃผ์ด์ง ๋ฐฐ์ด์ด [1,1,1,1,1] ์ผ๋
1, 1, 1, 1, 1
1, 1, 1, 1, -1
1, 1, 1, -1, 1
1, 1, 1, -1, -1
1, 1, -1, 1, 1
1, 1, -1, 1, -1
1, 1, -1, -1, 1
1, 1, -1, -1, -1
... ์ด๋ฐ ๋ฐฉ์์ ํธ๋ฆฌ ํํ๋ก ์งํ๋๋ค.
๊น์ด ์ฐ์ ํ์์ ๋ํ์ ์ธ ๊ธฐ๋ณธ ์์ ๋ผ๊ณ ํ ์ ์์๋งํ ๋ฌธ์ ์๋ค.
function solution(numbers, target) {
let answer = 0;
const dfs = (level, result) => {
if(level === numbers.length){
if(result === target) answer += 1;
return;
}
dfs(level + 1, result + numbers[level])
dfs(level + 1, result - numbers[level])
}
dfs(0,0);
return answer;
}
'์ฝ๋ฉํ ์คํธ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Javascript] ๊ตฌ๋ช ๋ณดํธ (42885) (0) | 2022.06.11 |
---|---|
[Javascript] ์์ ์ฐพ๊ธฐ (42839) (0) | 2022.06.11 |
[Javascript] ๊ฐ์ฅ ํฐ ์ (42726) (0) | 2022.06.11 |
[Javascript] ์์ ๋ง๋ค๊ธฐ (12977) (0) | 2022.06.10 |
[Javascript] 2016๋ (12901) (0) | 2022.06.06 |