[백준] 1463번 1로 만들기 - 파이썬(Python)

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

1463번: 1로 만들기

 

문제

 

접근법

 

처음엔 x가 2로 나눠질 때, 3으로 나눠질 때, -1로 빼기를 if문으로 했었는데 입력받은 수 10일 때 안됨을 확인했음.

반례가 바로 다행히 나와서 다른 접근법을 구상해야했고, 동적 알고리즘은 처음 접하기에 사용법 검색

 

동적 접근법, 즉 다이나믹 프로그래밍은 memoization을 주로 활용

같은 것을 계속 반복하면 시간을 잡아먹으니 한번 찾은 건 저장해놓음으로써  반복의 횟수를 줄여주는 방식

다이나믹 프로그래밍은 상향식, 하향식이 존재

이 문제는 입력받은 수까지의 여정을 그리는 게 나아 상향식 접근법 사용

 

입력받은 수까지 있는 list 생성

2부터 입력받은 수까지 이동

-1하는 거와, 2로 나누는 거와, 3으로 나누는 거 중 더 작은 수 사용

(+1들을 해주는 이유는, 전 경우의 수에서 현재 경우의 수로 오며 1이 더해지는 거기 때문)

 

코드

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

for i in range(2,x+1):
	# -1했을 때의 경우
    arr[i]=arr[i-1]+1
    
    if i%2==0:
    	# -1했을 때와 2로 나눴을 때를 비교
        arr[i]=min(arr[i],arr[i//2]+1)

    if i%3==0:
    	# -1했을 때와 3으로 나눴을 때를 비교
        arr[i]=min(arr[i],arr[i//3]+1)


print(arr[x])