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

문제

나의 답안

n=int(input())

dq=[0]*(n+1)#입력받은 숫자만큼의 길이를 갖는, 0으로 초기화 된 배열을 생성
#dq는 1로 만드는데 걸리는 횟수를 저장한다.

for i in range(2,n+1):
    dq[i]=dq[i-1]+1 #2와 3으로 나뉘지 않는 경우=> 1로 빼준다
    if i%3==0:#3으로 나뉘는 경우
        dq[i]=min(dq[i],dq[i//3]+1) #나눈 횟수를 저장하기 위해 1을 더함

    if i%2==0:#2로 나뉘는 경우
        dq[i]=min(dq[i],dq[i//2]+1)#기존 횟수와 현재 계산한 횟수 비교        
print(dq[n])#n과 대응되는 배열의 인덱스를 찾는다.
#인덱스의 값은 연산의 최소횟수와 대응됨

#점화식 : dq(N) = min(dq(N//3)+1, dq(N//2)+1 , dq(N-1)+1)

접근방법

• 10같은 경우에는 10 -> 9 -> 3 -> 1 또는, 10 -> 5 -> 4 -> 2 -> 1 으로 계산될 수 있으나 전자가 이동횟수가 더 적다.
• 세 경우에서, 2와 3으로 나뉘지 않는 경우에선 -1을 해주어야 한다.
• 나뉜다면 -1을 굳이 할 필요없으므로(나누는게 더 이득), 나누어준다.
• 계산 횟수가 필요한 것이므로 나눴을 땐 +1을 더한 값을 계산해주고, dq배열에 저장 해준다.