[DP] python 12852 1로 만들기2

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

12852번: 1로 만들기 2

# 2023.01.30
import sys
input = sys.stdin.readline

n = int(input())
dp=[[0]*(2) for _ in range(n+1)]  #연산을 하는 횟수의 최솟값
dp[1][0]=0 # 연산횟수
dp[1][1]=[1] # 연산순서

# n~1 dp table탐색
for i in range(2, n+1):
    dp[i][0]=dp[i-1][0]+1 # 연산횟수
    dp[i][1]=dp[i-1][1]+[i] # 연산순서
    if i%3==0 and dp[i//3][0]+1 < dp[i][0]: # 3으로 나눌 수 있고, 연산횟수가 더 작으면 
        dp[i][0]=dp[i//3][0]+1
        dp[i][1]=dp[i//3][1]+[i]
    if i%2==0 and dp[i//2][0]+1 < dp[i][0]: # 2로 나눌 수 있고, 연산 횟수가 더 작으면
        dp[i][0]=dp[i//2][0]+1
        dp[i][1]=dp[i//2][1]+[i]
print(dp[n][0])
print(*reversed(dp[n][1]))

---

[참고: 연산의 순서가 왜 1을 먼저 계산해두고 i%3과 i%2를 고려해야 할까?]

https://jae04099.tistory.com/199

[파이썬] 백준 - 1463: 1로 만들기 (매우 자세한 해설 포함)

dp: 메모이제이션 사용

dp - 상향식, 하향식

상향식: 제일 작은 인덱스의 수부터 목표하는 값으로 향하는 것

하향식: 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것

 

dp와 greedy와의 차이점

greedy: 처음 생각한 최적의 방법이 끝까지 반례없이 적용되는 경우

dp: 모든 가능성을 두고 그 안에서 최솟값을 찾음 - 정해진 최선의 연산 방법이 없기 때문에 다 시도해보아야 한다

 

왜 1을 먼저 빼고 시작하는가?

1을 먼저 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 갱신되기 때문

결국에는 3으로 나누는 방법, 2로 나누는 방법, 1을 빼는 방법 3가지 경우를 모두 시도하게 된다

if 문만 사용하여야 3가지 연산을 모두 수행할 수 있다