๋ฌธ์ ๐ฝ
https://school.programmers.co.kr/learn/courses/30/lessons/154538
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๋ค๋ฅธ์ฌ๋ ํ์ด ๐ฝ
function solution(x, y, n) {
if (x === y) return 0;
const dp = {};
dp[x] = 0;
let data = [x];
while (data.length) {
const newData = [];
for (const d of data) {
for (const e of [d + n, d * 2, d * 3]) {
if (e > y || dp[e]) continue;
if (e === y) return dp[d] + 1;
dp[e] = dp[d] + 1;
newData.push(e);
}
}
data = newData;
}
return -1;
}
๋ดํ์ด๐ฝ
1. ์ฒซ์๋ ์คํจ โ -> ๋ฐํ์ ์๋ฌ(์๊ฐ ์ด๊ณผ)
function solution(x, y, n) {
var answer = 0;
const countList = []
const dfs = (x,count)=>{
if(x==y){
countList.push(count)
return
}if(x>y){
return
}
dfs(x+n,count+1)
dfs(x*2,count+1)
dfs(x*3,count+1)
}
dfs(x,0)
if(countList.length){
answer=Math.min(...countList)
}else{
answer = -1;
}
return answer;
}
๐ฝ ์๋์ ๊ฐ์ด ์๋ฌ๊ฐ ๋ธ
2. ๋๋ฒ์งธ ์๋ > ๐ฏ ์ฑ๊ณต
function solution(x, y, n) {
if(x===y){
return 0;
}else if(x>y){
return -1;
}
let countArray = Array(y+1).fill(Infinity)
countArray[x] = 0;
for(i=x+1; i<y+1; ++i){
if(i-n>=x){
countArray[i] = Math.min(countArray[i],countArray[i-n]+1)
}
if(i%2===0&&i/2>=x){
countArray[i] = Math.min(countArray[i],countArray[i/2]+1)
}
if(i%3===0&&i/3>=x){
countArray[i] = Math.min(countArray[i],countArray[i/3]+1)
}
}
return countArray[y]===Infinity? -1:countArray[y]
}
๋๋์ ๐ฎ
์ฒ์์ผ๋ก DFS ( Depth first search ) ๋ผ๋ ๊ฐ๋ ์ ์ ํ ์ ์๋ ๋ฌธ์ ์๋ค. DFS/BFS ์ด๋ฐ ์ฉ์ด๋ค์ด ์๋๋ฐ ์ฉ์ด๋ ๋ชฐ๋ผ๋ ๋๊ณ ๊ทธ ๊ฐ๋ ์ ์ฒด๋ํ๋ฉด ๋ ๊ฒ ๊ฐ๋ค. 2๋ฒ์งธ code ์์ฑ ์ > ๋ค๋ฅธ์ฌ๋์ code๋ฅผ ์ฐธ๊ณ ํ์ฌ ์์ฑ ํ์๋๋ฐ ํด๋น๊ณผ ๊ฐ์ ์๊ณ ๋ฆฌ์ฆ์ ํผ ์ ์ด ์์ด์ ์จ์ ํ ์ดํดํ๋๋ฐ ์ค๋ ๊ฑธ๋ ธ๋ค.