DP 알고리즘 개념 및 연습문제1

DP 개념 공부

DP 개념 공부하기

이 선생님 강의 너무 좋다. 한 번에 DP를 이해할 수 있었다.
하지만, 개념은 알겠는데 문제에 적용하는 게 ...ㅎ_ㅎ

연습문제 1

🏆 백준 1463번 - 1로 만들기 (실버 III)

📌 문제 설명

정수 N이 주어질 때, 다음 3가지 연산을 사용할 수 있다.
1. N이 3으로 나누어 떨어지면 N / 3
2. N이 2로 나누어 떨어지면 N / 2
3. N - 1

위 연산을 이용하여 N을 1로 만들 때, 최소 연산 횟수를 구하시오.

---

📌 접근 방식

🔹 1. 그리디 접근 ❌

• "3으로 먼저 나누고, 안 되면 2로 나누고, 안 되면 -1" 하는 그리디 방식은 최적해를 보장하지 않음.
• 예를 들어 10 → 5 → 4 → 2 → 1 (총 4번)이지만, 10 → 9 → 3 → 1 (총 3번)이 더 최적해!

🔹 2. DP(다이나믹 프로그래밍) 활용 ✅

• dp[i]를 "i를 1로 만들기 위한 최소 연산 횟수"라고 정의
• 점화식:

  dp[i] = min(dp[i - 1] + 1, dp[i // 2] + 1 (if i % 2 == 0), dp[i // 3] + 1 (if i % 3 == 0))

📌 제출 코드

n = int(input())
dp = [0] * (n + 1)

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1  # 기본적으로 -1 연산
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)  # 2로 나누는 경우
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)  # 3으로 나누는 경우

print(dp[n])

📌 연산 과정 예시 (n=10)

i	dp[i]	최적 경로
1	0	시작점
2	1	2 → 1 (÷2)
3	1	3 → 1 (÷3)
4	2	4 → 2 → 1 (÷2, ÷2)
5	3	5 → 4 → 2 → 1 (-1, ÷2, ÷2)
6	2	6 → 3 → 1 (÷3, ÷3)
7	3	7 → 6 → 3 → 1 (-1, ÷3, ÷3)
8	3	8 → 4 → 2 → 1 (÷2, ÷2)
9	2	9 → 3 → 1 (÷3, ÷3)
10	3	10 → 9 → 3 → 1 (-1, ÷3)

다음 연습문제도 DP다!!