https://www.acmicpc.net/problem/1463

🥚문제

---

🥚입력/출력

---

🍳코드

import sys

n = int(sys.stdin.readline())
# dptable 초기화
dptable = [0 for i in range(1000001)]

for x in range(1, n+1):
    if x == 1:
        # 1은 1로 만들지 않아도 1. 따라서 연산횟수 0
        dptable[x] = 0
        continue

    if dptable[x] != 0:
        continue
    else:
        count_list = [] # 최소 연산 횟수를 구하기 위함
        # 3의 배수이면 dptable[x//3]+1의 연산횟수
        if x % 3 == 0:
            count_list.append(dptable[x//3] + 1)
        # 2의 배수이면 dptable[x//2]+1의 연산횟수
        if x % 2 == 0:
            count_list.append(dptable[x//2] + 1)
        # dptable[x-1]+1의 연산횟수도 테스트
        count_list.append(dptable[x-1] + 1)

        # 연산 횟수의 최소를 dptable에 저장
        dptable[x] = min(count_list)

print(dptable[n])

📌 핵심은 if문 두 개로 3의 배수일 경우, 2의 배수일 경우 모두 검사하고, 1을 빼는 경우의 연산 횟수도 검사해서 그 중 최소 연산 횟수를 table에 저장하는 것이다.
📌 또한, '1로 만들기' 이므로 input이 1일 때 output은 1이 아닌 0이어야 한다. 연산 조건 3번에서 "1을 뺀다." 가 있어서 1이면 1을 뺄 수 있으니까 연산 횟수가 1이라고 착각하면 안된다!

---

🧂아이디어

• 사진에서 23일 전이라고 떠 있는 것은 아마도 이 문제를 brute force, greedy로 풀 수 있을거라고 착각한 시절의 코드

• dynamic programming으로 풀었는데, 틀렸습니다가 떴다. 100%까지 채점됐다가 틀렸습니다가 떠서 당황했다. 알고보니 input이 1일 때는 연산 횟수가 0이어야 하는데, 1로 초기화해서 틀렸던 거였다. "1로 만들기" 이니까 input이 1이면 아무 연산 안해도 되는데!

• 케이스를 더 꼼꼼히 생각해보고 코드를 짜야겠다.

🔼본 문제의 전반적인 아이디어