💡 문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 10보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
💭 접근
주어진 수를 3으로 나누거나, 2로 나누거나, 1을 빼는 연산의 최소한의 횟수로 1을 만드는 문제이다. 이때, 예제를 살펴보면,
ex) 예제
X = 10, 10 -> 9 -> 3 -> 1
X = 9, 9 -> 3 -> 1
X = 3, 3 -> 1
이와같이 10을 구할 땐 9의 결과를, 9를 구할 땐 3의 결과를 사용하는 것을 알 수 있다. 또한 2와 3으로 나누어 떨어지지 않는 경우엔 1을 빼주는 연산이 필요하기 때문에 처음 dp[i]의 값을
dp[i - 1] - 1 로 초기화해준다.
이 문제를 풀면서 주의해야 할 것이 있다. 문제를 처음 접하면 큰 수로 처음부터 나누는 것이 제일 빠르게 1을 만들 수 있다고 생각할 수 있다. 그러나 똑같이 예제를 살펴보면,
ex) 예제
X = 10, 10 -> 5 -> 4 -> 2 -> 1
이처럼 1을 빼고 시작하는 것보다 많은 연산을 거치게 되므로 먼저 1을 뺀 수와 2 또는 3으로 바로 나눈 수의 최소값을 비교해 주어야한다.
📒 코드
n = int(input())
dp = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
dp[i] = dp[i - 1] + 1
if i % 3 == 0:
dp[i] = min(dp[i], dp[i//3] + 1)
if i % 2 == 0:
dp[i] = min(dp[i], dp[i//2] + 1)
print(dp[n])💭 후기
DP를 공부하고 처음 풀어본 문제라서 조금 헤맸던 것 같다. 문제의 패턴을 보고 점화식을 구하는 연습을 많이 해야겠다.
🔗 문제 출처
https://www.acmicpc.net/problem/1463
