[백준] 1로 만들기

[백준] 1로 만들기

문제

링크 : 백준

---

풀이

문제는 어떤 수가 주어졌을 때, 다음과 조건에서 연산이 가능하다고 한다.
여기서 1로 갈 수 있는 최단의 연산을 구하는 것이다.

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

이 문제는 dp(dynamic programming)으로 가능한 문제이기에 풀어보려 한다. (처음엔 dfs를 활용해서 문제를 풀었다. 하지만, 수가 많아졌을 때 메모리 사용이 많아져 메모리 초과가 뜬다!)

점화식을 구해서 일반화 시켜 메모제이션하면 된다.
점화식을 구할 때는 헷갈리기에.. 예를 몇 개 넣어보면서 맞는 지 판단한다.
모든 과정을 생각하지말고 결과만 보자

X = int(input())
d = [0] * (10**6 + 1)
ans = 0
for i in range(2, X+1):
    d[i] = d[i-1] + 1
    if i % 2 == 0:
        d[i] = min(d[i],d[i//2]+1)
    if i % 3 == 0:
        d[i] = min(d[i],d[i//3]+1)
print(d[X])

---

실수 및 배운 점

• 점화식을 구할 때 계속 헷갈리는 부분이 생긴다.
  모든 과정을 파악하려고 한다. 결과가 생길 수 있는 경우의 수만 생각해보면 될 것 같다.