[백준(BOJ) / Python] 1463번: 1로 만들기

문제 링크: www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

문제 설명

시간 내에 문제를 풀기 위해선 동적 계획법(Dynamic Programming)을 이용해 문제를 해결해야 한다. 

1로 만들기 위한 연산 횟수를 저장하는 dp테이블을 만들고 dp[1]부터 dp[n]까지를 계산한다. 

 

dp[1] = 0

dp[2] = dp[1] + 1  // 2로 나누거나 1을 빼기

dp[3] = dp[1] + 1  // 3으로 나누기

dp[4] = dp[2] + 1 = dp[3] + 1  // 2로 나누거나 1을 빼기

dp[5] = dp[4] + 1  // 1을 빼기

dp[6] = dp[2] + 1 = dp[3] + 1  // 2로 나누거나 3으로 나누기

.

.

 

이때 주의할 점은 dp[6] 같은 경우 3으로도 나눠지고 2로도 나눠지고 1을 빼는 연산도 가능하다. 하지만 이 중에서 연산 횟수가 최소가 되는 경우를 dp에 저장해야 한다. 코드에서는 min함수를 이용해 이를 구현했다. 

 

 

 

소스코드

n = int(input())
INF = 987654321
# 1로 만들기 위한 연산 횟수를 저장하는 dp 테이블
dp = [INF] * (n + 1)
dp[1] = 0

for i in range(2, n + 1):
    # 3으로 나누는 연산
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    # 2로 나누는 연산
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)
    # 1을 빼는 연산
    dp[i] = min(dp[i], dp[i - 1] + 1)

print(dp[n])