[동적계획법/DP] 백준 1463 1로 만들기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1463번: 1로 만들기

 

 

 

2. 문제 풀이

 1) 3으로 나누기
 2) 2로 나누기
 3) 1을 빼기

 

 3가지 연산을 최소로 사용해서 N을 1로 만드는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 DP문제입니다. 그리디처럼 [ 3으로 나누기 > 2로 나누기 > 1 빼기 ] 순으로 우선순위를 둘 수 없습니다. 10의 경우, 2로 나누기보다 1을 뺀 후 3으로 나누는 게 더 빠릅니다.

 

 

 

3. 코드

N = int(input())
cache = [0]*(N+1) #메모이제이션

for i in range(2, N+1):
    # 1을 뺐을 때
    cache[i] = cache[i-1] + 1

    # 2로 나누었을 때
    if i % 2 == 0:
        cache[i] = min(cache[i], cache[i//2]+1)

    # 3으로 나누었을 때
    if i % 3 == 0:
        cache[i] = min(cache[i], cache[i//3]+1)
print(cache[N])

 가능한 연산은 총 3가지입니다. 각각의 연산을 수행했을 때, 필요한 연산 횟수를 모두 계산합니다.

 현재의 연산 횟수(cache[i])와 해당 연산 수행 시 연산 횟수를 비교해서 작은 걸로 대체합니다.

 if-else문이 아니라, if문으로 나열한 이유는 3가지 경우를 모두 고려해서 계산하기 때문입니다.