[Python] 백준1463 1로 만들기

04 Jan 2023 in Study on Algorithm

백준1463 1로 만들기 링크

문제

예제 입력

---

코드

n = int(input())
arr = [ 0 ] * (n + 1)

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

print(arr[n])

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list을 사용하여 dp알고리즘으로 1로 만들기를 구현했습니다.

---

정리

n = int(input())
arr = [ ]

def serch_num(num, cnt) :
    if num == 1 :
        return arr.append(cnt)
    
    if num % 3 == 0:
        serch_num(num // 3, cnt + 1)
    if num % 2 == 0:
        serch_num(num // 2, cnt + 1)

    serch_num(num - 1, cnt + 1)

serch_num(n, 0)
print(min(arr))

처음에는 자료형 list를 사용하여 재귀함수로 구현했는데 시간 초과가 발생했습니다.

---

결과