[Baekjoon] 1463 - 1로 만들기

🔗 Problem Link

1463번: 1로 만들기

---

❔Thinking

• "2로 나누기 / 3으로 나누기 / 1빼기" 이 3가지 방법으로 주어진 숫자를 1로 만든다.
• 해당 숫자를 1로 만드는 다양한 방법 가운데, 가장 적은 횟수로 1을 만들고 그 횟수를 반환한다. 

---

💻Solution

n = int(input())
how_to_make_n = [0, 0, 1, 1]
for i in range(4,n+1):
    if i % 3 == 0 and i % 2 == 0:
        how_to_make_n += [min(1+how_to_make_n[i-1], how_to_make_n[i//3] + 1, how_to_make_n[i//2] + 1)]
        continue
    if i % 3 == 0:
        how_to_make_n += [min(1+how_to_make_n[i-1], how_to_make_n[i//3] + 1)]
        continue
    if i % 2 == 0:
        how_to_make_n += [min(1+how_to_make_n[i-1], how_to_make_n[i//2] + 1)]
        continue
    how_to_make_n += [how_to_make_n[i-1] + 1]
print(how_to_make_n[n])

---

🗝️keypoint

1. 주어진 숫자가 1이 될 때까지 연산을 계속하면, 시간초과가 발생한다.
2. DP를 통해, 매번 가장 작은 숫자로 만들어야 한다. (3으로 나눈 수 < 2로 나눈 수 < 1을 뺀 수)
3. 2와 3 모두로 나누어 지는 수는, 모든 경우를 확인하고 가장 작은 횟수를 저장한다.