다이나믹 프로그래밍 - 1 로 만들기

1 로 만들기 (Python)

📝 문제 설명

정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 입니다.

1. X가 5로 나누어 떨어지면, 5로 나눕니다.
2. X가 3으로 나누어 떨어지면, 3으로 나눕니다.
3. X가 2로 나누어 떨어지면, 2로 나눕니다.
4. X에서 1을 뺍니다.
   정수 X가 주어졌을 때, 연산 4개를 적절히 활용해서 값을 1로 만들고자 합니다.
   연산을 사용하는 횟수의 최솟값을 출력하세요.

예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다.
26 -> 25 -> 5 -> 1

---

📌 조건

• 입력 조건
  • 첫째 줄에 정수 X가 주어집니다.
    • 1 <= X <= 30,000
• 출력 조건
  • 첫째 줄에 연산을 하는 횟수의 최소값을 출력합니다.

---

🔽 입력 예시

26

🔼 출력 예시

3

---

🏆 정답 코드

def 모범답안():
    x = int(input())
    d = [0] * 3001
    for i in range(2, x + 1):
        d[i] = d[i - 1] + 1
        if i % 2 == 0:
            d[i] = min(d[i], d[i // 2] + 1)
        if i % 3 == 0:
            d[i] = min(d[i], d[i // 3] + 1)
        if i % 5 == 0:
            d[i] = min(d[i], d[i // 5] + 1)
    return d[x]

---

🔥 느낀 점

• 4가지 연산 방식이 있고 x 가 1일 때, 2일 때 ... 쭈욱 나아가면서 각 자연수 마다 최적의 해를 구하는 dp 문제이다.
• 4가지 연산 방법에 따라서 최적의 해(최소 연산 횟수) 를 기록한다.
  • -1 연산을 하는 경우
    • x 가 1인 경우 연산 횟수 0
    • x 가 2인 경우 연산 횟수 1
    • x 가 3인 경우 연산 횟수는 x가 2인 경우 연산 횟수의 + 1 이다.
    • x 가 4인 경우 연산 횟수는 x가 3인 경우 연산 횟수의 + 1 이다.
  • x 를 2로 나누는 연산을 하는 경우 (if x % 2 == 0)
    • x 가 1인 경우 연산 횟수 0
    • x 가 2인 경우 연산 횟수 1
    • x 가 4인 경우 연산 횟수는 x가 2일 경우 연산 횟수의 + 1 이다.
    • x 가 8인 경우 연산 횟수는 x가 4일 경우 연산 횟수의 + 1 이다.
  • x 를 3으로 나누는 연산을 하는 경우 (if x % 3 == 0)
    • ...
  • 이렇게 나아가면서 연산 방법중 최소값을 최적의 해로 기록한다..
• 각 자연수에 따라서 최적의 해를 기록해 놓으면 그 다음 연산 방법에 따른 최적의 해는 이전 최적의 해 값에 + 1 이 된다.