[Python] 백준 #1463- 1로 만들기

문제

---

1463번: 1로 만들기

코드

---

My answer

n=int(input())

d=[0]*(n+1)
d[1]=0

for i in range(2,n+1):
    tmpa,tmpb=n,n
    if(i%2==0):
        tmpa=d[i//2]+1
    if(i%3==0):
        tmpb=d[i//3]+1
    tmpc=d[i-1]+1
    d[i]=min(tmpa,tmpb,tmpc)
print(d[n])

Another answer

n = int(input())
li = [0]*(n+1)  # 0,1,2,...,n
li[1] = 0

for i in range(2,n+1) :
  li[i] = min((li[i//3]+i%3+1),(li[i//2]+i%2+1))

print(li[n])

 

풀이

---

이 문제는 동적프로그래밍으로 푸는 문제였다 동적프로그래밍은 나중에 알고리즘에 따로 작성하도록 하겠다.

우선 규칙을 발견하고 앞에서부터 차례대로 구해나간다. 어차피 규칙은 하나이므로 아래코드와 윗코드 동일한데, 아래코드는 한줄에 표현하도록 식을 더 잘정리한 것 같다. 동적프로그래밍 문제를 풀 때는 우선 앞에서부터 규칙을 찾아나가면서 풀어나가야한다.