[백준] 파이썬 1463번 1로 만들기

- 문제: (1.3일)

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

1463번: 1로 만들기

- 코드: DP문제는 처음이라,, 되는 확률들의 횟수를 다 따로 저장해서 비교하는 방식으로 해야한다. 머릿속으로는 생각했는데 어떻게 해야할지 아예 감이 안잡혔다ㅠㅠ 상향식 하향식 방식이 있는데 상향식이 더 코드는 이해하기 쉬웠다.  DP 알고리즘에 대해서 따로 정리하기! 

n = int(input())
cnt = 0
while n>0:
    if n%3==0:
        n = n//3
        cnt+=1
        if n==1:
            break
        if n%2==0:
            n = n//2
            cnt+=1
    if n%2==0:
        n = n//2
        cnt+=1
        if n==1:
            break
        if n%3==0:
            n = n//3
            cnt+=1
    n = n-1
    cnt +=1
print(cnt)

- 정답 코드:

n = int(input())
d = [0] * (n + 1)	## d에 계산된 값을 저장해둔다. n + 1이라고 한 이유는, 1번째 수는 사실 d[1]이 아니고 d[2]이기 때문에, 계산하기 편하게 d[1]을 1번째 인 것 처럼 만들어준다.

print(d)
for i in range(2, n + 1): #11
## 여기서 왜 if 1빼는 방법, 2 나누기, 3 나누기 동등하게 하지 않고 처음에 1을 빼고 시작하는지 의아해 할 수 있다.
## 1을 빼고 시작하는 이유는 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문이다.
## 즉 셋 다 시도하는 방법이 맞다.
## 여기서 if elif else를 사용하면 안된다. if만 이용해야 세 연산을 다 거칠 수 있다, 가끔 if continue, else continue를 쓰는 분도 계신데, 난 이게 편한듯.
    d[i] = d[i - 1] + 1
    print(d[i])
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)	## 1을 더하는 것은 d는 결과가 아닌 계산한 횟수를 저장하는 것 이기 때문이다. d[i]에는 더하지 않는 이유는 이미 1을 뺄 때 1을 더해준 이력이 있기 때문이다.
        print(d)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
        print(d)
print(d[n])