백준 1463번 1로 만들기 (JavaScript 풀이)

[백준 1463] 1로 만들기 - 동적 프로그래밍

📖 동적 프로그래밍(DP) 

정의: 큰 문제를 작은 문제들로 나누어 해결하는 알고리즘
특징: 작은 문제들의 답을 저장해두고 재사용
핵심: "큰 문제 = 작은 문제들의 조합"

🔄 문제 해결 과정

큰 문제: N을 1로 만들기
     ↓ (나누기)
작은 문제들: N/3을 1로 만들기, N/2를 1로 만들기, N-1을 1로 만들기
     ↓ (조합)
답: 작은 문제들의 답 중 최솟값 + 1

---

📌 문제 요약
정수 N에 세 가지 연산을 사용해서 1을 만드는 최소 연산 횟수를 구하는 문제.

• 연산 1: 3으로 나누어떨어지면 3으로 나누기
• 연산 2: 2로 나누어떨어지면 2로 나누기
• 연산 3: 1 빼기

입력: N (1 ≤ N ≤ 1,000,000)
출력: 최소 연산 횟수

출처: https://www.acmicpc.net/problem/1463

---

💡 문제 접근

작은 예시들로 패턴 찾기

🟢 N=1: 이미 1 → 0번
🔵 N=2: 2÷2=1 → 1번
🟡 N=3: 3÷3=1 → 1번
🔴 N=4: 4÷2=2, 2÷2=1 → 2번
🟠 N=5: 5-1=4, 4는 2번 → 3번
🟣 N=6: 6÷3=2(1번) 또는 6÷2=3(1번) → 2번

---

N=6 자세한 분석

6을 1로 만드는 방법들:
1) 6÷3=2 → 2를 1로 만드는데 1번 → 총 1+1=2번
2) 6÷2=3 → 3을 1로 만드는데 1번 → 총 1+1=2번  
3) 6-1=5 → 5를 1로 만드는데 3번 → 총 1+3=4번

최소값: min(2, 2, 4) = 2번

---

공식 발견!

dp[n] = n을 1로 만드는 최소 연산 횟수

dp[n] = 1 + min(
    dp[n/3]  (n이 3으로 나누어떨어질 때)
    dp[n/2]  (n이 2로 나누어떨어질 때)  
    dp[n-1]  (항상 가능)
)

---

N=10 단계별 계산 과정

         dp[10] = ?
            |
    1 + min( dp[9], dp[5] )
            |      |
           2      3
            
dp[10] = 1 + min(2, 3) = 3

---

작은 것부터 차례로:

dp[1]=0, dp[2]=1, dp[3]=1, dp[4]=2, dp[5]=3
dp[6]=2, dp[7]=3, dp[8]=3, dp[9]=2, dp[10]=3

 

---

📝 풀이 코드 (JavaScript)

const fs = require('fs');
const N = +fs.readFileSync(0, 'utf8').trim();

// dp[i] = i를 1로 만드는 최소 연산 횟수
const dp = new Array(N + 1);
dp[1] = 0;

for (let i = 2; i <= N; i++) {
    // 1 빼기 (항상 가능)
    dp[i] = dp[i - 1] + 1;
    
    // 2로 나누어떨어지면 비교
    if (i % 2 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 2] + 1);
    }
    
    // 3으로 나누어떨어지면 비교
    if (i % 3 === 0) {
        dp[i] = Math.min(dp[i], dp[i / 3] + 1);
    }
}

console.log(dp[N]);

---

🔎 풀이 해설

단계별 실행 과정:

1. dp 배열 생성: dp[i] = i를 1로 만드는 최소 연산 횟수
2. 초기값 설정: dp[1] = 0 (1은 이미 1이므로)
3. Bottom-up 계산: 2부터 N까지 차례로 계산
4. 각 i에 대해: - 일단 dp[i-1] + 1 (1 빼기) - i%2==0이면 dp[i/2] + 1과 비교 - i%3==0이면 dp[i/3] + 1과 비교 - 이 중 최솟값이 dp[i]
5. 답 출력: dp[N]

효율성:

• 시간복잡도: O(N) - 각 숫자를 한 번씩만 계산
• 공간복잡도: O(N) - dp 배열 하나만 사용
• 핵심: 작은 문제의 답을 재사용해서 중복 계산 방지

---

💭 내 생각

• 처음엔 "모든 경우를 다 해봐야 하나?" 했는데, 작은 것부터 차례로 하니까 쉬워짐!
• N=6에서 6÷3=2, 6÷2=3 둘 다 같은 결과가 나오는 게 신기했음
• DP의 핵심은 "이미 계산한 걸 또 계산하지 말자"인 것 같다
• 큰 문제를 작은 문제로 나누는 아이디어가 정말 똑똑함

---

📚 배운 점

• Bottom-up DP: 작은 문제부터 차례로 해결해서 큰 문제 해결
• 최적 부분 구조: 큰 문제의 최적해가 작은 문제들의 최적해로 구성됨
• 상태 정의: dp[i]를 명확히 정의하는 것의 중요성
• 점화식 도출: 문제의 조건을 수식으로 표현하는 능력
• 그리디 vs DP: 그리디는 매 순간 최선, DP는 모든 경우 고려 후 최선