1로 만들기 문제 / 타뷸레이션(bottom up)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

 

타뷸레이션(bottom up)

N=int(input())

memo = [0] * (N + 1) # 인덱스 N 까지 만들기 위해


for i in range(2, N+1):    # index 0과 1은 값이 0이기 때문에 2부터 시작
    
    memo[i] = memo[i-1] + 1  

    if i % 2 == 0:
        memo[i] = min(memo[i], memo[i // 2] + 1)

    if i % 3 == 0:
        memo[i] = min(memo[i], memo[i // 3] + 1)


print(memo)
print(memo[N])

 

풀이 

0과 1은 연산을 사용하는 횟수가 필요없으므로 출력 값은 0이다.

그러므로 memo[0] 과 memo[1] 의 값은 0

memo = [0] * (N + 1)

로 memo[0]과 memo[1]은 이미 0 이므로 for문을 2부터 시작한다.

 

2는 2로 한번 나눠주면 1이 되므로 연산 사용 횟수가 1이다.

memo[2] = memo[2 // 1] + 1

 

memo[2 // 1] 은 memo[1]이므로

memo[2 // 1] + 1은 0 + 1이 된다.

그러므로 memo[2] = 2

 

3도 같은 요령으로 3으로 한번만 나눠주면 1이 되기 때문에

memo[3] = memo[3 // 1] + 1

 

그런데 만약 입력이 10이라면

2로 먼저 나누는 것 보다

1로 먼저 빼는 것이 연산 사용 횟수가 적다.

 

10을 2로 먼저 나누면 5 4 2 1 로 연산 사용 횟수 4번

 

10에서 1을 먼저 빼주면 9 3 1 로 연산 사용 횟수 3번이다.

 

그러므로 i가 2로 나누어 떨어진다면

min(memo[i], memo[i // 2])

 

i가 3으로 나누어 떨어진다면

min(memo[i], memo[i // 3])

 

 

 이렇게 해주면 i = 10 이라면

memo[10] = memo[9] + 1

# memo[9] = 2 이므로 memo[10] = 3

이 된다.

 

즉 memo[i]에서 1을 빼줘서 memo[i-1] 이 되는 것이 최소값의 경로라면 그 경로의 값이 나오고

 

2나 3으로 나누는 것이 최소값의 경로라면 2나 3으로 나누어 주게 되는 것이다.