[BOJ] 1로 만들기 (no.1463)

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

🤔 생각

• dp 문제는 처음에 케이스를 잘 나누는게 중요하다.

• 점화식 구상할 땐 top-down 방식으로 생각하는게 더 수월한것 같다.

• 3으로 나누어지면 반드시 3으로 나누란 얘기가 아니고, 세가지 경우를 모두 적용할 수 있다는 말이다. 처음에 전자로 이해해버려서 삽질했다... (바본가)

케이스

1. 3으로 나누어 떨어지는 경우
2. 2로 나누어 떨어지는 경우
3. 그 외

배열 정의

dp[i] : 정수 i일 때 최소 연산 횟수

🔥 점화식

dp[i] = min(dp[i//3]+1, dp[i//2]+1, dp[i-1]+1)
논리가 대략 이렇다는거고 그대로 쓰면 안된다.
2나 3으로 나누어지는지 확인도 해야하므로 조건문으로 추가 처리 해주면 된다.

📌 내 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*(n+1)

for i in range(2,n+1):
    dp[i] = dp[i-1] + 1
    if i%3 == 0 and dp[i] > dp[i//3]+1: dp[i] = dp[i//3]+1
    if i%2 == 0 and dp[i] > dp[i//2]+1: dp[i] = dp[i//2]+1

print(dp[n])

✔ 회고

• 짜고 나면 허무할 정도로 쉽지만 아직 점화식 구상이 서툴다.
• 어려워도 결국엔 고이게 될거다! DP 쭉쭉 밀자