백준 #1463 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

n=int(input())

a=0

while n!=1:

    if n%3==0:

        n/=3

        a+=1

    elif n%2==0:

        n/=2

        a+=1

    else:

        n-=1

        a+=1

       

print(a)

(틀렸습니다.)

 

arr=[[1]]

a=0

n=int(input())

for i in range(n):    

        for j in range(len(arr[i])):

            arr_2=[arr[i][j]+1, arr[i][j]*2, arr[i][j]*3]

            arr.append(arr_2)

            if n in arr[-1]:

                break

        if n in arr[-1]:

            break

       

k=len(arr)

a=1

b=0

while True:

    a+=3**b

    b+=1

   

    if k<=a:

        break

if n==1:

    print(0)

else:

    print(b)

(메모리 초과)

 

arr=[1]

n=int(input())

k=0

for i in arr:

    if i+1  not in arr:

        arr.append(i+1)

    if i*2 not in arr:

        arr.append(i*2)

    if i*3 not in arr:

        arr.append(i*3)

    if n in arr:

        break

    if 3**k in arr:

        k+=1

if n==1:

    print(0)

elif n==2 or n==3:

    print(1)

elif n==4 or n==6:

    print(2)

else:

    print(k)

(시간 초과)

 

n=int(input())

arr=[[]for _ in range(n)]

arr[0].append(n)

for i in range(1,n):

    for j in arr[i-1]:

        arr[i].append(j-1)

        if j%2==0:

            arr[i].append(j//2)

        if j%3==0:

            arr[i].append(j//3)

    if 1 in arr[i]:

        break

print(i)

(런타임 에러)

 

 

 

n=int(input())

arr=[[]for _ in range(n)]

arr[0].append(n)

a=0

for i in range(1,n):

    for j in arr[i-1]:

        arr[i].append(j-1)

        if j%2==0:

            arr[i].append(j//2)

        if j%3==0:

            arr[i].append(j//3)

    a+=1

    if 1 in arr[i]:

        break

print(a)

(맞은 풀이)

 

n=int(input())

arr=[0 for _ in range(n+1)]

for i in range(2, n+1):

    arr[i]=arr[i-1]+1

   

    if i%2==0:

        arr[i]=min(arr[i], arr[i//2]+1)

       

    if i%3==0:

        arr[i]=min(arr[i], arr[i//3]+1)

print(arr[n])

       

(수정)