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

문제

---

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

1463번: 1로 만들기

 

 

 

풀이

---

n = int(input())

d=[0]*(n+1)
d[1]=0
for i in range(2,n+1):
    arr=[]
    if i%3==0:arr.append(d[i//3]+1)
    if i%2==0:arr.append(d[i//2]+1)
    arr.append(d[i-1]+1)
    d[i] = min(arr)
print(d[n])

동적프로그래밍을 사용하였다. d를 만들어서 3으로 나누어질때, 2로 나누어질때를 구하고 -1을 할때도 구해준다.

이들 중에 최솟값을 구해준다.

 

 

 

[다른사람 코드] - 백준 숏코딩

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])

푼 방식은 비슷한데 한줄 코딩을 한 것이다. i%3을 더해주면 i-1을 추가로 할 필요가 없어진다.