오늘 푼 문제는 DP! 즉 Dynamic Programming!

DP란 큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로, 점화식같은 recursive coding 에 해당한당

일단 감을 잡는다는 거에 의의를 둔 하루,,, 또륵


1463

def make_one(num):
    if num%3 == 0:
        num /= 3
    elif num%2 == 0:
        num /= 2
    else:
        num-=1
    return num

a = int(input())
count = 0

while(a!=1):
    a = make_one(a)
    count += 1
print(count)

처음에는 엥 이정도 쯤이야! 하고 풀었지만 가차 없이 틀린 문제,,,

최소 횟수라는 점을 놓친것 같당 히히

그리고 좀 더 구글링해본 결과, 매번 재귀함수를 호출하는 것보다는

list를 이용하는게 속도 향상에 효과적이라는 단서도 얻었당!

a = int(input())
num = []
count = []


if(a!=1):
    if a%3 == 0:
        num.append(a/3)
        count.append(1)
    if a%2 == 0:
        num.append(a/2)
        count.append(1)
    num.append(a-1)
    count.append(1)

i = 0
while (1 not in num):
    if num[i]%3 == 0:
        num.append(num[i]/3)
        count.append(count[i]+1)
    if num[i]%2 == 0:
        num.append(num[i]/2)
        count.append(count[i]+1)
    num.append(num[i]-1)
    count.append(count[i]+1)
    i+=1
print(count[num.index(1.0)])

이걸 냈지만 시간 초과래 엉엉,,,,

# https://chunghyup.tistory.com/49 참고
def min(x, y):
    return x if x <= y else y

x = int(input())

minimum_count = [0 for _ in range(x+1)]

index = 0
while(True):
    if index > x:
        break

    if index <= 1:
        minimum_count[index] = 0
    else:
        temp_min = x + 1
        if index % 3 == 0:
            temp_index = int(index/3)
            temp_min = min(temp_min, minimum_count[temp_index])

        if index % 2 == 0:
            temp_index = int(index/2)
            temp_min = min(temp_min, minimum_count[temp_index])

        temp_min = min(temp_min, minimum_count[index-1])
        minimum_count[index] = int(temp_min + 1)
    index = index + 1

print(minimum_count[x])

그래서 이걸 참고했당 !

# https://elrion018.tistory.com/41 참고
X = int(input())
count = 0
result = [X]
def calculation(x):
    lst = []
    for i in x:
        lst.append(i-1)
        if i%3 ==0:
            lst.append(i/3)
        if i%2 ==0:
            lst.append(i/2)
    lst = set(lst)
    lst = list(lst)
    return lst
while True:
    if X == 1:
        break
    temp = result
    result = []
    result = calculation(temp)
    count += 1
    if min(result) == 1:
        break
print(count)