반응형
1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/154538#qna
2. 코드
처음 작성한 코드) 일부 타임 아웃
큐를 이용하지 않아서 타임아웃이 뜬건가 싶기도 하다ㅠㅠ 근데 큐를 이용하는 방법을 모르겠는걸
function solution(x, y, n) {
let answer = -1;
const bfs = (newY, total) => {
if(newY === x) {
if(answer !== -1) answer = answer > total ? total : answer;
else answer = total;
}
else if(x < newY){
if(newY - n >= x) bfs(newY - n,total+1);
if(newY / 2 >= x) bfs(newY / 2,total+1);
if(newY / 3 >= x) bfs(newY / 3,total+1);
else answer === -1;
}
}
bfs(y,0);
return answer;
}
정답 코드)
역시나 예상은 했지만 dp로 풀었어야 했다. dp가 왜 익숙해지지 않는걸까^^
기억하자..dp는 이전 값 저장에 포커스를 둔다...
function solution(x, y, n) {
if (x === y) return 0;
const dp = {};
dp[x] = 0; // 수들이 더하거나 곱해져 갈 때 바뀐 횟수 count하기 위해 이전 값에 횟수 저장해놓고 사용
let data = [x]; // 조건에 맞게 더하거나 곱해준 수
while (data.length) {
const newData = [];
for (const d of data) {
for (const e of [d + n, d * 2, d * 3]) {
// 새로운 수가 y보다 크거나
// 새로운 수가 이미 이전 순서에서 나왔을 때
if (e > y || dp[e]) continue;
// 새로운 수가 y와 같을 때 이전 숫자에 저장된 횟수 + 1 리턴
if (e === y) return dp[d] + 1;
// 새로운 수가 위 어느 조건에도 성립하지 않으면 이전 숫자에 저장된 횟수 + 1을 새로운 수의 값으로 저장
dp[e] = dp[d] + 1;
newData.push(e); // 비교 대상 리스트에 새로운 수 추가
}
}
data = newData; // 비교 대상 숫자 리스트 바꿔주기
}
return -1;
}
복기
6/14
반응형
'프로그래머스 > DP' 카테고리의 다른 글
[DP] 프로그래머스 '스티커 모으기(2)' - js (0) | 2023.05.11 |
---|---|
[피보나치] 프로그래머스 '2xn 타일링' - js (0) | 2023.04.22 |
[DP] 프로그래머스 '땅따먹기' - js (0) | 2023.04.11 |
[피보나치] 프로그래머스 '멀리뛰기' - js (0) | 2022.10.20 |