[BOJ] 1463. 1로 만들기

문제

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

1463번: 1로 만들기

 

 

---

 

주요 아이디어

1~n까지의 dp list를 만들고, 해당 숫자를 만들기 위해 필요한 최소 연산 횟수를 구하면 된다.

 

 

---

 

코드 구현 (Python 3)

 

n = int(input())

dp_list = [0] * (n+1)

# 1로 만들기니까 2 이상부터 시작
for i in range(2, n+1):
    # 기본적으로 할 수 있는 연산 = 이전 연산횟수에서 빼기 한번이므로 +1
    dp_list[i] = dp_list[i-1] + 1

    if i%2 == 0:
        # 이전 연산 (i*2) 에서 나누기 한번이므로 +1
        dp_list[i] = min(dp_list[i], dp_list[i//2]+1)
    if i%3==0:
        # 이전 연산 (i*3) 에서 나누기 한번이므로 +1
        dp_list[i] = min(dp_list[i], dp_list[i//3]+1) 

print(dp_list[n])

 

 

 

 

---

 

제출 결과