[백준_python] 1로 만들기 || 1463

www.acmicpc.net/problem/1463

1463번: 1로 만들기

이 문제는 다이나믹 프로그래밍과 관련된 문제이다.
 
다이나믹 프로그래밍이란?
큰 문제를 작은 문제로 나누어서 푸는 기법, 작은 부분 문제들이 반복되는 경우를 매번 재계산하지 않고 재사용을 하는 기법이라고 한다.
 
구현 방식으로는 bottom-up과 top-down이 있다.
bottom-up은 작은 문제부터 차근차근 푸는 것이고
top-down은 보통 우리가 아는 재귀 함수로, 큰 문제를 풀려하고 작은 문제가 풀리지 않았다면, 작은 문제를 푸는 방식이다.

---

2 → 1     3번째 연산을 1회 해준다.  
10 → 5 →4 →2→1이라는 방식도있지만, 10 → 9 → 3 → 1 이라는 더 적은 방식이 있다.
이처럼 1로 만들어지는 최소값을 구해주어야 한다.
점화식은 dp[n] = min(dp[n//3], dp[n//2], dp[i-1]) + 1 이다.

# 1로 만들기 (bottom-up)

N = int(input())

dp = [0 for _ in range(N+1)]  # N만큼의 리스트 생성

for i in range(2, N+1):  # 2부터 N까지 반복
    dp[i] = dp[i-1] + 1  # 3번 연산
    if i % 2 == 0 and dp[i] > dp[i//2] + 1:  # 3번보다 2번이 더 작은 경우
        dp[i] = dp[i//2] + 1
    if i % 3 == 0 and dp[i] > dp[i//3] + 1:  # 3번보다 1번이 더 작은 경우
        dp[i] = dp[i//3] + 1

print(dp[N])

3번 연산을 먼저 해준 후, 2로 나눈 것과 3으로 나눈 것 중 더 작은 것으로 선택되도록 해준다.
여기서 elif라고 해주었다가.. 틀렸다.. 각각 if문으로 꼭 모두 비교가 되도록 해주어야 했다.!
 
bottom-up으로 작은 것부터 차례대로 최소 경우가 되는 수를 넣어주며 N번째의 dp로 결과를 구해준다.
 
 
다음에 dp문제가 나오게 되면, 내 스스로 꼭 풀어보고 싶다 노력노력!
 
 
참고한 사이트)
infinitt.tistory.com/247

백준 (boj) 파이썬 - 1463 : 1로 만들기      (DP)