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

백준 (BOJ) 1463번
https://www.acmicpc.net/problem/1463

사용언어 : PYTHON

1.문제

2.풀이

다이나믹 프로그래밍 (Bottom up) 방식으로 풀어야 했다.

2-1.순환식을 세우기

순환식을 세우는 사고의 출발점은 '최적해의 일부분이 그 부분에 대한 최적해인가?' 라고 배웠다.
정수 N을 1로 만드는 최소 횟수를 구하는 함수를 D(N)이라고 하자.

최적해를 생각해보면 다음과 같다.

D(10)은 10을 2로 나눈 D(5)와, 10에서 1을 뺀 D(9)중 더 작은 값 + 2로 나누거나 1을 뺀 연산횟수 1과 같다.
D(12)는 12를 3으로 나눈 D(4)와, 12를 2로 나눈 D(5), 12에서 1을 뺀 D(11) 중 더 작은값 + 연산의 횟수 1과 같다.

'최적해의 일부분이 그 부분에 대한 최적해인가?'에 대해서 생각해보면
최적해D(10)의 일부분 D(5), D(9)는 그 부분에 대한 최적해가 맞다.
최적해D(12)의 일부분 D(4), D(5), D(11)도 그 부분에 대한 최적해가 맞다.

이제 순환식을 세워보았다.

여기서 주의해야 할 점이 있는데 n이 3 또는 2로 나눠떨어져야 D(n//3) 또는 D(n//2)를 할 수 있다.

2-2.base case로 수렴하는지 확인

위 그림에서 D(n//3), D(n//2), D(n-1)은 base case인 n==1이나 n==2로 수렴한다.

2-3.순환식을 계산

bottom-up 방식(순환식의 오른쪽에 등장하는 값이 왼쪽에 등장하는 값보다 먼저 계산)으로 연산을 하려면 빨간색 화살표와 같이 인덱스 오름차순으로 계산하면 된다.

3.코드

순환식을 bottom-up 방식으로 계산하기 위해서 for문을 사용하여 구현하면 다음과 같다.
이때 -1연산 d[i] = 1 + d[i-1]은 어떤 정수이던지 가능하기 때문에 제일 처음 수행하도록 작성했다.
다음으로 3또는 2로 나누는 연산은 i가 3또는 2로 나눠떨어져야 하기때문에 if문으로 검사를 해줬다.
추가로 min값을 구하기 위해 if문에 and 조건으로 크기를 비교했다.

import sys
input = sys.stdin.readline

N=int(input())

d=[0]*(N+1)


for i in range(1,N+1):
    if i==1:
        d[i]=0
    elif i==2:
        d[i]=1
    else:
        d[i] = 1 + d[i-1]
        if i%3==0 and d[i]>1+d[i//3]:
            d[i]=1+d[i//3]
        if i%2==0 and d[i]>1+d[i//2]:
            d[i]=1+d[i//2]

print(d[N])