백준 1463: 1로 만들기

📊 결과

💻 내 코드 (Try 1)

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N+1];
        dp[1]=0;
        for(int i=2; i<N+1; i++){
            int cur = i;
            if( i%2 != 0 && i%3 != 0) {
                dp[i] = dp[cur - 1] + 1;
            }else if(cur%3==0){
                int prev = dp[cur/3];
                if(cur%2==0){
                    prev = Math.min(dp[cur/3], dp[cur/2]);
                }
                dp[i] = Math.min(prev, dp[cur-1]) + 1;
            }else if(cur%2==0){
                dp[i] = Math.min(dp[cur/2], dp[cur-1]) + 1;
            }
        }

        System.out.println(dp[N]);
    }
}

📝 평가

✔ 잘한 점

  1. Bottom-up DP 접근
    • 1부터 N까지 순차적으로 최솟값 계산
    • 메모이제이션으로 중복 계산 방지
  2. 세 가지 연산 모두 고려
    • 3으로 나누기, 2로 나누기, 1 빼기
    • 각 경우의 최솟값 선택
  3. 조건 분기 처리
    • 나눗셈 가능 여부 체크
    • 6의 배수(2와 3 모두) 처리

✦ 개선점

1. 과도한 조건 분기

// ✘ 복잡한 if-else 체인
if( i%2 != 0 && i%3 != 0) {
    dp[i] = dp[cur - 1] + 1;
}else if(cur%3==0){
    int prev = dp[cur/3];
    if(cur%2==0){
        prev = Math.min(dp[cur/3], dp[cur/2]);
    }
    dp[i] = Math.min(prev, dp[cur-1]) + 1;
}else if(cur%2==0){
    dp[i] = Math.min(dp[cur/2], dp[cur-1]) + 1;
}

모든 경우를 통합하면 더 간결하다.

2. 불필요한 변수

int cur = i;  // i를 그대로 사용 가능

3. 가독성

중첩된 조건문으로 로직 파악이 어렵다.

✨ 최적화된 풀이

import java.io.*;

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N+1];
        
        for(int 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);
            }
        }

        System.out.println(dp[N]);
    }
}

변경 사항:

성능 비교

방법 시간복잡도 공간복잡도 코드 길이
원본 O(N) O(N) 25줄
개선 O(N) O(N) 15줄

💡 핵심 인사이트

DP 점화식

dp[i] = 1 + min(
    dp[i-1],           // 1 빼기
    dp[i/2] (i%2==0),  // 2로 나누기
    dp[i/3] (i%3==0)   // 3으로 나누기
)

Greedy가 안 되는 이유

10 → 9 → 3 → 1 (3번)  ✔
10 → 5 → 4 → 2 → 1 (4번)  ✘

항상 나누기가 최선은 아니다. 모든 경로를 고려해야 한다.

설계 원칙

  1. 기본 연산(1 빼기)을 초기값으로
  2. 추가 연산 가능 시 최솟값 갱신
  3. 조건 독립적으로 처리

📚 관련 개념

🎓 다음 단계

유사 문제

  1. 백준 2579: 계단 오르기
  2. 백준 1003: 피보나치 함수
  3. 백준 9095: 1, 2, 3 더하기

연습 포인트

🏷️ Keywords

#백준 #DP #동적계획법 #BOJ1463 #Java #알고리즘