다이나믹 프로그래밍 연습문제 - 1로 만들기

🍎 1로 만들기

🏀 문제

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

 

   a. X가 5로 나누어 떨어지면, 5로 나눈다.

   b. X가 3으로 나누어 떨어지면, 3로 나눈다.

   c. X가 2로 나누어 떨어지면, 2로 나눈다.

 

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

⚾ 코드

num = int(input())
INF = 1e9
dp = [INF] * (num+1)

for i in range(2, num+1):
    if i == 1:
        dp[i] = 0
    elif i == 2 or i == 3 or i == 5:
        dp[i] = 1
    else:

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

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

        if i % 5 == 0:
            dp[i] = min(dp[i], dp[i//5]+1)

        dp[i] = min(dp[i], dp[i-1]+1)


print(dp[num])

 

🔔 해결 과정 & 깨달은 점

- bottom-up 방식의 다이나믹 프로그래밍 방식으로 풀었다.

- 문제를 보고, 1부터 차근차근 올라가면 좋겠다는 생각을 했기 때문이다.

- -1을 하는 코드를 else 바로 밑에 두고, d[i] = d[i-1]+1 이렇게 작성했다면, DP테이블을 INF 값으로 초기화 하지 않아도 됐을 뿐더러, 그 행에서는 min을 사용하지 않아도 됐을 것이다.

 

---

출처

📚 이것이 취업을 위한 코딩 테스트다 with 파이썬