b12852. 1로 만들기 2

https://www.acmicpc.net/problem/12852

 

 

 

📌 자바(Java)로 푸는 1로 만들기 2 - 백준 12852 🔢

최소 연산 횟수 + 경로 추적까지 하는 DP 문제!

 

---

🔎 문제 개요

 

백준 12852번 - 1로 만들기 2 문제는

정수 N이 주어졌을 때,

1로 만들기 위해 사용할 수 있는 연산은 다음 세 가지입니다:

 

1. X → X / 3 (3으로 나누어떨어질 때만)
2. X → X / 2 (2로 나누어떨어질 때만)
3. X → X - 1

 

최소 연산 횟수를 출력하고

그 경로에 해당하는 숫자 순서도 출력해야 합니다.

 

---

💡 예제 입력

10

 

💡 예제 출력

3
10 9 3 1

 

 

---

🛠 알고리즘 접근 방식: Dynamic Programming (DP)

 

 

✏️ 핵심 전략

 

• dp[i]: i를 1로 만들기 위한 최소 연산 횟수
• check[i]: i에 오기 직전의 수 (경로 추적용)

 

---

🔹 Java 코드 설명

 

 

📌 기본 초기화

dp[1] = 0;

✔ 1은 이미 목표값이므로 연산 횟수 0

 

---

📌 반복문으로 dp 채우기

for (int i = 2; i <= N; i++) {
    dp[i] = dp[i - 1] + 1;
    check[i] = i - 1;

    if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
        dp[i] = dp[i / 3] + 1;
        check[i] = i / 3;
    }

    if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
        dp[i] = dp[i / 2] + 1;
        check[i] = i / 2;
    }
}

✔ 현재 수 i는

 

• i-1
• i/2
• i/3✔ check[i]를 통해 최단 경로의 이전 수 저장
• 중 최소 연산 경로를 선택

 

---

📌 경로 추적

sb.append(dp[N]).append("\n").append(N).append(" ");
while (N > 1) {
    sb.append(check[N]).append(" ");
    N = check[N];
}

✔ dp값을 출력하고

✔ check[] 배열을 따라 거슬러 올라가며 경로를 재구성

 

---

🏆 정리

✅ 핵심 포인트

• DP[i] = min(DP[i-1], DP[i/2], DP[i/3]) + 1
• check[i] 배열을 통해 경로 추적까지 가능
• 경로 출력이 추가된 1로 만들기 확장판

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊