[BaekJoon] 1로 만들기(JavaScript)

📘 오늘의 코딩테스트 - 1로 만들기(JavaScript)

🔢 문제 번호: 1463번

🔗 문제 링크: 백준 - 1로 만들기

 

 

 

 

🧠 문제 요약

• 정수 N이 주어졌을 때, 다음과 같은 연산 세 개를 적절히 사용해 1을 만들려고 한다
• 연산을 사용하는 횟수의 최솟값을 출력하시오 
  • X가 3으로 나누어 떨어지면 3으로 나눈다
  • X가 2로 나누어 떨어지면 2로 나눈다
  • 1을 뺀다
• 입력: 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N
• 출력: 연산을 하는 횟수의 최솟값

 

 

 

✅ 실행 예시 및 결과

입력: 10
출력: 3

 

 

 

✍️ 내 풀이

• 다이나믹 프로그래밍(DP: Dynamic Programming)을 사용!!
• dp 배열을 생성하여 for문으로 결과를 dp에 저장
• 입력값을 dp 배열에서 찾아 출력!!

 

 

 

💻 내가 푼 코드

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim();

const N = parseInt(input);

// dp[i] = 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수
// 크기가 N+1인 배열을 준비(인덱스 1부터 사용)
const dp = new Array(N + 1);
// 1은 이미 1이므로 연산 횟수는 0
dp[1] = 0;

// 2부터 N까지 반복하면서 최소 연산 횟수를 채움
for (let i = 2; i <= N; i++) {
  dp[i] = Math.min(
    // 1을 빼는 경우
    dp[i - 1] + 1,
    // 2로 나누어 떨어지면 2로 나누는 경우
    i % 2 === 0 ? dp[i / 2] + 1 : Infinity,
    // 3으로 나누어 떨어지면 3으로 나누는 경우
    i % 3 === 0 ? dp[i / 3] + 1 : Infinity
  );
}

console.log(dp[N]);

 

 

 

📎 남이 푼 코드

// BFS 방식 - 레벨별로 탐색해서 최단거리 찾기
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input);

function solution(n) {
    // queue: [숫자, 연산횟수] 형태로 저장
    const queue = [[n, 0]];  // 시작: [10, 0] (10에서 시작, 0번 연산)
    const visited = new Set(); // 이미 방문한 숫자들 기록
    
    while (queue.length > 0) {
        // 큐에서 하나씩 꺼내기
        const [current, count] = queue.shift(); // [10, 0] → current=10, count=0
        
        // 1에 도달하면 연산횟수 반환
        if (current === 1) return count;
        
        // 이미 방문했으면 건너뛰기 (중복 방지)
        if (visited.has(current)) continue;
        visited.add(current); // 방문 표시
        
        // 가능한 모든 연산을 큐에 추가 (다음 레벨)
        queue.push([current - 1, count + 1]);  // 1빼기: [9, 1]
        if (current % 2 === 0) queue.push([current / 2, count + 1]); // 2로나누기: [5, 1]
        if (current % 3 === 0) queue.push([current / 3, count + 1]); // 3으로나누기
    }
}

console.log(solution(N));

• BFS(너비 우선 탐색): 연못에 돌 던지면 동심원이 퍼지듯이, 시작점에서 레벨별로 확산하며 탐색하는 알고리즘
• 큐를 사용해서 0레벨 → 1레벨 → 2레벨 →3레벨..... 레벨별로 탐색하므로
• 가장 먼저 목표에 도달하는 순간이 바로 최단거리!!
• DP보다 직관적이지만 메모리를 더 사용
• 둘 다 같은 답이지만 BFS는 "실제 경로 따라가기", DP는 "작은 문제 쌓아올리기" 방식

 

 

🔍 회고 & 배운 점

• 처음에는 +1이 왜 붙는지 이해가 안됐는데 손으로 1, 2, 3, 4,.... 해보니까 이해할 수 있었다!!
• DP의 핵심은 "작은 문제의 최적회를 활용해서 큰 문제 해결하기"를 다시 복습했다!!
• 다음에 DP문제 나오면 지금보다 빨리 이해할 수 있을 것 같다 헿