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

문제 보러 가기!

아이디어 🌼

처음에는 DFS로 코드를 짰다. 2, 10 정도는 금방 답이 나왔지만...
N의 범위가 10의 6제곱... 10000 정도만 해도 시간이 오래 걸렸다. 또 지금 생각해보니, 최대 재귀 깊이를 초과할 수 있겠다는 생각도 든다..!

다시 짠 코드 !
3가지 종류의 계산이 있는데, 가능한 계산을 하고, 그 중에 가장 횟수가 적은 것을 dp에 넣는다!

코드 📝

N = int(input())
dp = [0, 0, 1, 1] + [0] * N  # 0, 1번 인덱스는 편하게 쓰려고 추가. 2에서 1로 가는 최소 연산 수는 1, 3에서 1로 가는 최소 연산 수는 1개.

for i in range(4, N + 1):  # N을 구해야 하니까 그때까지 보기
    if i % 6 == 0:  # i가 2, 3으로 나누어 떨어지는 경우 -> 연산 1, 2, 3 중에 가장 횟수 적은 것을 dp에 저장
        dp[i] = min(1 + dp[i // 3], 1 + dp[i // 2], 1 + dp[i - 1])
    elif i % 2 == 0:  # i가 3으로는 나누어 떨어지지 않고, 2로 나누어 떨어지는 경우 -> 연산 2, 3 중에 가장 횟수 적은 것을 dp에 저장
        dp[i] = min(1 + dp[i // 2], 1 + dp[i - 1])
    elif i % 3 == 0:  # i가 2로는 나누어 떨어지지 않고, 3으로 나누어 떨어지는 경우 -> 연산 1, 3 중에 가장 횟수 적은 것을 dp에 저장
        dp[i] = min(1 + dp[i // 3], 1 + dp[i - 1])
    else:  # i가 2나 3으로 나누어 떨어지지 않는 경우 -> 연산 3
        dp[i] = 1 + dp[i - 1]
# print(dp)
print(dp[N])