[콭] 점프와 순간 이동 - DP x

강원지·2023년 4월 23일

코테

코테 다시보기

목록 보기

21/22

코딩테스트 연습
Summer/Winter Coding(~2018)
점프와 순간 이동

점프와 순간 이동

문제

점프 또는 순간이동을 하여 n의 자리로 이동할 때의 건전지 사용량의 최소를 구하시오.
점프로 이동할 때는 +1이 소모되고 순간이동 할 때는 건전지가 소모되지 않는다.

첫 번째 풀이 (시간 초과)

접근방법

dp를 이용한 풀이.
1부터 시작해서 *2 또는 +1을 한 값을 큐에 넣고 dp에 이동 최소값을 저장함.

숫자 N은 최대 10억이라는 조건을 지나쳤다. 때문에 효율성 채점에서 모두 시간 초과가 떴다.

javascript 오답코드


function solution(n) {
  let ans = 0;
  const dp = {};

  let queue = [];
  let visited = Array(n).fill(0);

  queue.push([1, 1]);

  while (queue.length) {
    let [cur, cnt] = queue.shift();
    
    if (cur === n) {
      ans = cnt;
      break;
    }
    if (cur > n) continue;
    
    if (visited[cur]) dp[cur] = Math.min(cnt, dp[cur]);
    else dp[cur] = cnt;
    
    visited[cur] = 1;

    queue.push([cur * 2, cnt]);
    queue.push([cur + 1, cnt + 1]);
  } 
    return ans
}

두 번째 풀이

접근방법

첫 번째 풀이와 비교도 안 되게 간단하다.
n부터 시작해서 /2를 수행하고 나머지가 발생한다면 -1을 하여 1에 도달할 때까지의 이동값을 구하면 된다.

javascript 정답코드

function solution(n) {
  let ans = 1;
  
    while(n!==1){ 
        if(n%2===0){
            n=n/2
        }else{
            n--
            ans++
        }
    }
    
    return ans
}